Ways to Decode a Digit String
A message of capital letters was turned into digits with this code: A → 1, B → 2, and so on up to Z → 26. The digits were written one after another with no spaces.
You get the digit string s. Return how many different letter messages could give exactly s.
Rules for reading the digits:
- Every digit must be used, in order.
- A group of one digit must be
1to9. A single0is not a letter. - A group of two digits must be
10to26. A group that starts with0, such as05, is not a letter.
If s cannot be read at all, return 0.
Hint
Let ways[i] be the number of readings of the first i digits, with ways[0] = 1. The last group is either one digit or two digits. Add ways[i - 1] if the last digit alone is valid, and add ways[i - 2] if the last two digits together are valid.
Examples
Example 1
- Input:
- "2214"
- Output:
- 5
The readings are 2 2 1 4, 22 1 4, 2 21 4, 2 2 14 and 22 14. That is 5.
Example 2
- Input:
- "1203"
- Output:
- 1
The 0 must join the 2 before it as 20, so the 1 stands alone and so does the 3. Only 1 20 3 works.
Example 3
- Input:
- "508"
- Output:
- 0
The 0 cannot stand alone, and 50 and 08 are not letters. No reading exists.
Constraints
1 <= s.length <= 30scontains only the digits0to9.- The answer is at most about 1.4 million.
Run checks your code against the 3 examples. Submit checks it against all 263 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.