The problem
Letters are encoded as numbers: A is 1, B is 2, …, Z is 26. A string of digits can often be read back several ways — 12 is AB (1, 2) or L (12).
Given the digits s, return the number of ways to decode it. A group may not start with 0, so 06 cannot be read.
Examples
- Input
s = "12"
- Output
2
- Input
s = "226"
- Output
3
- Input
s = "06"
- Output
0
Constraints
- 1 ≤ s.length ≤ 100
scontains only digits and may start with 0.
The idea
Let ways(i) count the decodings of the digits from position i to the end. The first letter uses either one digit — any of 1–9 — leaving ways(i + 1); or two digits forming 10–26, leaving ways(i + 2).
So ways(i) = [s[i] ≠ 0] · ways(i + 1) + [s[i..i+1] is 10–26] · ways(i + 2), where [ ] is 1 when true and 0 when false, and the empty end decodes exactly one way. Fill it from the end backwards, keeping two values. For 226, working from the end: the empty end is 1 way; 6 is 1; 26 is 1 + 1 = 2 (2 6, or 26); 226 is 2 + 1 = 3.
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def numDecodings(self, s: str) -> int: # ways(i): decodings of s[i:]. A letter is one digit 1-9, or two digits 10-26. # ways(i) = [s[i] != "0"] * ways(i + 1) + [s[i:i+2] in 10..26] * ways(i + 2) nxt, nxt2 = 1, 0 # ways(i + 1), ways(i + 2); the empty end decodes one way for i in range(len(s) - 1, -1, -1): cur = 0 if s[i] != "0": cur = nxt if i + 1 < len(s) and 10 <= int(s[i : i + 2]) <= 26: cur += nxt2 nxt, nxt2 = cur, nxt return nxt