Decode Ways
Problem Statement
A message containing digits is encoded by mapping A to 1, B to 2, and so on through Z to 26. Given a digit string s, return the number of ways to decode it. A group with a leading zero is invalid, and 0 can only appear as part of 10 or 20.
Input
A digit string s.
Output
An integer: the number of valid decodings of the entire string.
Constraints
- •
1 <= s.length <= 100 - •
s contains only digits and may contain leading zeroes
Examples
Example 1
s = 12
2Example 2
s = 226
3Example 3
s = 06
0Learning Objectives
- Define DP over prefix length rather than over the current character alone.
- Add contributions only when the one-digit or two-digit choice is valid.
- Handle zeroes correctly without special-case explosions.
- Compress the prefix-count table to two rolling counts.
Intuition
Think of decoding as walking through the string. At position i, the final decoded letter could use just the last digit, or it could use the last two digits. Those are the only possibilities because codes are from 1 through 26.
The tricky part is validity. A single digit contributes only if it is 1 through 9. A two-digit group contributes only if it is between 10 and 26. When a choice is valid, it appends one letter to every decoding of the remaining prefix, so it adds the count from the matching earlier prefix.
Common mistakes
- ×Treating **0** as a valid single-digit code.
- ×Accepting two-digit groups like **06** or **30**.
- ×Defining **dp[i]** as ending at index **i** and then mixing it with prefix-length indices.
- ×Replacing addition with max; this problem counts all valid choices, not the best choice.
- ×Forgetting that **dp[0] = 1** represents the empty prefix needed by valid two-digit decodings at the start.
State Definition
Let dp[i] be the number of ways to decode the prefix of length i, meaning s[0...i - 1]. The answer is dp[n].
State Transition
For prefix length i, consider the final one or two digits:
- If s[i - 1] is between 1 and 9, add dp[i - 1].
- If s[i - 2...i - 1] is between 10 and 26, add dp[i - 2].
So dp[i] is the sum of the valid contributions. Base cases are dp[0] = 1 for the empty prefix and dp[1] = 1 only if the first character is not 0, otherwise 0.
Solutions
Solution: Prefix DP with two rolling counts
Keep the number of decodings for the previous prefix length and the prefix length two positions back. Each new position adds one or both counts depending on valid one-digit and two-digit endings.
Step-by-step
- Initialise twoPositionsBack = 1 for the empty prefix.
- Initialise onePositionBack based on whether the first digit is nonzero.
- For each prefix length from 2 to n, start current at 0.
- Add onePositionBack if the last digit is valid alone, and add twoPositionsBack if the last two digits form a valid code.
- Roll the two counts forward and return the final previous-prefix count.
O(n)
O(1)
Each character is examined a constant number of times with two stored counts.
Java implementation
Dry Run
Sample input
s = 226. Use prefix lengths, with dp[0] = 1 and dp[1] = 1 for the prefix 2.
| i | prefix | single digit contribution | two digit contribution | dp[i] |
|---|---|---|---|---|
| 2 | 22 | 2 is valid, add 1 | 22 is valid, add 1 | 2 |
| 3 | 226 | 6 is valid, add 2 | 26 is valid, add 1 | 3 |
The final prefix count is 3, representing 2 + 2 + 6, 22 + 6, and 2 + 26.
Complexity Analysis
Decode Ways is still a constant-window 1D DP, but the recurrence is conditional because zeroes and values above 26 are invalid.
Prefix DP with two rolling counts
O(n)
O(1)
Each character is examined a constant number of times with two stored counts.
Interview Tips
Say that dp[i] counts decodings of a prefix of length i. That avoids off-by-one confusion and makes the two contributions obvious. Spend extra time explaining zero: 0 is never valid alone, while 10 and 20 are valid two-digit codes.
Likely follow-ups
- How would you return the actual decoded strings for small inputs?
- What changes if the mapping extends beyond 26?
- How would you handle wildcard characters that can represent any digit?
- How would you validate the input early if non-digit characters were allowed?
Similar Problems
Key Takeaways
- Prefix-length state makes string DP transitions cleaner than raw character indices.
- Single-digit and two-digit endings contribute only when they are valid codes.
- The empty prefix count **dp[0] = 1** is essential for two-digit decodings at the beginning.
- Zero handling is the core edge case: **0** alone is invalid, but **10** and **20** are valid.