Decode Ways
MediumDynamic Programming · Google
Letters are encoded as numbers: "A" is "1", "B" is "2", and so on up to "Z" as "26". You are given a string s of digits produced this way, with the separators removed.
Return the number of ways to split s into pieces so that every piece is a valid code from "1" to "26". Every digit must be used. A piece cannot have a leading zero, so "0" on its own and "05" are invalid, and "27" or higher is invalid. If there is no valid way, return 0.
Example 1
- Input:
- s = "1126"
- Output:
- 5
- Explanation
- The five splits are 1|1|2|6, 11|2|6, 1|12|6, 1|1|26 and 11|26.
Example 2
- Input:
- s = "11106"
- Output:
- 2
- Explanation
- The
0must pair with the1before it as10, which fixes the middle. The only splits are 1|1|10|6 and 11|10|6.
Example 3
- Input:
- s = "30"
- Output:
- 0
- Explanation
30is above 26 and0alone is not a code, so the0cannot be placed anywhere.
Constraints
- 1 ≤
s.length≤ 100 scontains only digits and may start with0- The answer fits in a signed 32-bit integer