Problem 28.6 · DP Foundations: 1DMedium

Decode Ways

What it teaches: Counting with validity checks: one-digit and two-digit transitions, careful with zeros.

Practise it on judges as “Decode Ways”.

The problem

Letters A–Z are encoded as "1"–"26". Return the number of ways to decode a digit string.

Example 1

Input: s = "226"
Output: 3

2 2 6, 22 6, 2 26.

Example 2

Input: s = "06"
Output: 0

Constraints

1 ≤ length ≤ 100

Pattern clues in the wording

→ Count ways to split a string with rules

These clues point to 1D Dynamic Programming: Define dp[i] as the answer for the first i items, write how it depends on smaller i, and fill it left to right.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int numDecodings(String s) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	s = "12"	2
2	s = "226"	3
3	s = "06"	0

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Prefix DP · O(n)

Prefix DP

Time O(n) Space O(n), or O(1) with two variables

dp[0] = 1. For each i, combine the one-character and two-character endings when valid.

Approach 1

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];
            if (i >= 2) {
                int two = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
                if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

Verdict: The zero rules are the whole difficulty.

Before you submit

Edge cases and common mistakes

Test these inputs

Leading zero (0)
"10", "20" (only the pair works)
"30" (0)

Mistakes people make

Counting "06" as a two-digit code.

Interview

Follow-up questions

What if '*' can stand for any digit 1–9 (Decode Ways II)?

Command Palette

The problem

Approaches

Prefix DP

Edge cases and common mistakes

Follow-up questions