Given a string of digits, the machine must count the ways to decode it into letters, where '1' through '26' map to 'A' through 'Z'. Each digit can stand alone or form a two-digit number with the digit before it, and every character must be consumed exactly once.
The key insight is the same decomposition used in Fibonacci problems: a valid decoding of the prefix ending at position i either ends with a single digit at position i, or with a two-digit pair spanning i-1 and i. The machine sums the counts of both options, so ways(i) = ways(i-1) + ways(i-2), with constraints on what each option is allowed to decode to.
The approach runs in three steps. First, initialize dp[0] = 1 for the empty prefix and set dp[1] based on whether the first digit is nonzero. Second, for each position, add dp[i-1] when the current digit is not '0', and add dp[i-2] when the two-digit number lies between 10 and 26 inclusive. Third, return dp[n]. Time is O(n) and space is O(n), compressible to two variables.
The trickiest edge case is the leading zero: a single '0' is not a valid letter, and any number starting with '0' is outside 10-26, so "06" decodes to 0 ways. The pair constraint is inclusive — "10" and "26" count, but "27" and "01" do not.
def numDecodings(s):
dp = [0] * (len(s) + 1)
dp[0] = 1
dp[1] = 0 if s[0] == "0" else 1
for i in range(2, len(s) + 1):
if s[i - 1] != "0":
dp[i] += dp[i - 1]
if 10 <= int(s[i - 2:i]) <= 26:
dp[i] += dp[i - 2]
return dp[len(s)]