Decode Ways
Medium · dynamic programming
A message was written by replacing each letter with its position in the alphabet: A is 1, B is 2, and so on up to Z is 26. All the numbers were then glued together into one string of digits s. Nothing marks where one number ends and the next begins, so the same string can often be read in more than one way.
Return the number of different ways to split s into numbers between 1 and 26. A number cannot start with 0, so "06" is not 6, and "0" on its own is not a letter. If no valid reading exists (for example when s starts with 0), return 0.
Examples
Example 1
Input: s = "12"
Output: 2
Read it as 1 and 2 (AB), or as 12 (L). Two ways.
Example 2
Input: s = "226"
Output: 3
2 2 6 (BBF), 22 6 (VF), or 2 26 (BZ). 226 is too big to be a letter.
Example 3
Input: s = "06"
Output: 0
A number cannot start with 0, and 06 is not allowed either, so nothing can be read.
Constraints
- 1 <= len(s) <= 40
- s contains only the digits 0 to 9, and may start with 0.
- The answer always fits in a 32-bit signed integer.