Decode Ways

medium1D Dynamic Programming27 stepsJava · Python · C++

Count how many ways a digit string can be decoded with A=1 … Z=26. At each position, the last letter used either one digit (1–9) or two digits (10–26). dp[i] = (one-digit valid ? dp[i−1] : 0) + (two-digit valid ? dp[i−2] : 0).

▶ Watch the animated trace

Traced input: s = "226" → 3. Original problem: neetcode.io/problems/decode-ways

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(n)

Can be reduced to two variables.

Key idea

'0' can't stand alone; it must be part of 10 or 20.
Two digits are valid only from 10 to 26.
dp[0] = 1 (empty string has one decoding) makes the recurrence work.

Common mistakes

Treating "06" as a valid two-digit code.
Forgetting that a leading '0' makes the whole string undecodable.

Solution

Java

int numDecodings(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        int one = s.charAt(i - 1) - '0';
        if (one != 0) dp[i] += dp[i - 1];
        if (i >= 2) {
            int two = Integer.parseInt(s.substring(i - 2, i));
            if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
        }
    }
    return dp[n];
}

Python

def numDecodings(s: str) -> int:
    n = len(s)
    dp = [1] + [0] * n
    for i in range(1, n + 1):
        if s[i - 1] != '0': dp[i] += dp[i - 1]
        if i >= 2 and 10 <= int(s[i - 2:i]) <= 26: dp[i] += dp[i - 2]
    return dp[n]

C++

int numDecodings(string s) {
    int n = s.size();
    vector<int> dp(n + 1);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] != '0') dp[i] += dp[i - 1];
        if (i >= 2) {
            int two = stoi(s.substr(i - 2, 2));
            if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
        }
    }
    return dp[n];
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Leading zero '0' alone is invalid and "06" isn't a letter.	`s = "06"`	`0`
Zero inside Only "J".	`s = "10"`	`1`
Bad zero The second 0 can't attach to anything valid.	`s = "100"`	`0`
Mixed AAJF or KJF.	`s = "11106"`	`2`