Decode Ways

Count how many ways a digit string can map to letters (A=1..Z=26). Each position can be decoded alone (if 1-9) or combined with the previous digit (if 10-26) — a Fibonacci-shaped recurrence with validity checks.

Category: Dynamic Programming
Time complexity: O(n)
Space complexity: O(n)

Pseudocode

dp[0] = 1, dp[1] = 1 if s[0]≠0
dp[i] += dp[i−1] if s[i−1] is 1-9
dp[i] += dp[i−2] if s[i-2..i] is 10-26
answer at dp[n]

Reference implementation

dp = [1] * 2
for i in range(2, n + 1):
    ways = 0
    if s[i-1] != '0': ways += dp[i-1]
    if 10 &lt;= int(s[i-2:i]) &lt;= 26: ways += dp[i-2]
    dp.append(ways)

Open the interactive Decode Ways visualisation →