Loading problem…
Given a string s containing only digits, return the number of ways to decode it. 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26.
Example 1
Input: s = 12321
Output: 6
Explanation: "12321" can be split as 1-2-3-2-1, 12-3-2-1, 1-23-2-1, 1-2-3-21, 12-3-21 and 1-23-21. "32" is not a valid letter (above 26), so there are 6 decodings.
Example 2
Input: s = 12
Output: 2
Explanation: "12" can be read as "AB" (1 2) or "L" (12), giving 2 ways.
Example 3
Input: s = 226
Output: 3
Explanation: "226" can be read as "BZ" (2 26), "VF" (22 6) or "BBF" (2 2 6), giving 3 ways.
Define `dp[i]` = number of ways to decode the prefix `s[:i]`. The very last decoded letter consumes either one digit (`'1'..'9'`) — contributing `dp[i-1]` ways — or two digits (`'10'..'26'`) — contributing `dp[i-2]`. Add the valid contributions. Like Fibonacci, only the last two states matter, so two scalars suffice.
Run checks all cases above. Submit evaluates all test cases.