Letters are encoded as numbers: A is 1, B is 2, and so on up to Z as 26. Given a string s of digits, return the number of ways to decode it back into letters.
A group can't start with 0: 06 isn't a valid code for F. If s can't be decoded at all, return 0.
Examples
Example 1
- Input
- s = "12"
- Output
- 2
- Why
- It can be read as AB (1 2) or L (12).
Example 2
- Input
- s = "226"
- Output
- 3
- Why
- BZ (2 26), VF (22 6), or BBF (2 2 6).
Example 3
- Input
- s = "06"
- Output
- 0
- Why
- No group can start with 0.
Constraints
1 <= s.length <= 100scontains only digits, and may contain leading zeros.