A message of capital letters was turned into digits with A → 1, B → 2, …, Z → 26,
and the codes were written one after another with no gaps. So "126" could have come from ABF
(1 2 6), AZ (1 26) or LF (12 6).
Given the string of digits s, return the number of ways to decode it. No code starts with 0:
"06" can't be read as F, and a 0 can't stand on its own, so some strings can't be decoded
at all and the answer is 0.
Example 1
- Input
- s = "126"
- Output
- 3
ABF (1 2 6), AZ (1 26) and LF (12 6).Example 2
- Input
- s = "2101"
- Output
- 1
0 must pair with the 1 before it, which leaves only 2 10 1 (BJA).Example 3
- Input
- s = "30"
- Output
- 0
0 can't be read on its own.Constraints
sholds 1 to 70 digits, and may contain0s anywhere, including at the start.- The answer is below 2⁵³.
Show the pattern
Dynamic programming (1D)
The last letter of any decoding comes from the last digit or from the last two, so the count for a prefix is built from the counts for the two shorter prefixes.
See dynamic programming (1d) in a visualiserShow the approach
Let ways[i] be the number of decodings of the first i digits. Every decoding of that prefix
ends with a letter made from either:
- the last digit alone, allowed when it isn't
0: that addsways[i − 1]; - the last two digits together, allowed when they read a number from 10 to 26 (so not
05): that addsways[i − 2].
Start with ways[0] = 1 and walk along the string. Each value needs only the two before it, so
keep two variables instead of the table. A 0 that can't pair with the digit before it makes
the count 0, and it stays 0 from then on.
Time: O(n) · Space: O(1)