DP over positions: decode one digit or two digits when valid.
Let dp[i] = ways to decode prefix ending at i.
Transition:
s[i] != '0', add dp[i-1].10 <= int(s[i-1..i]) <= 26, add dp[i-2].
Use rolling variables for O(1) space.Any valid decoding ends with either a single-letter code or a two-letter code.
DP over positions: decode one digit or two digits when valid.
Let dp[i] = ways to decode prefix ending at i.
Transition:
s[i] != '0', add dp[i-1].10 <= int(s[i-1..i]) <= 26, add dp[i-2].
Use rolling variables for O(1) space.Any valid decoding ends with either a single-letter code or a two-letter code.