Decode Ways Problem: How Do You Solve It?
Learn to solve the decode ways problem with dynamic programming, digit validity checks, and O(1) space optimization.
Expected Interview Answer
The decode ways problem — counting how many ways a digit string can be decoded to letters where "1" maps to "A" through "26" maps to "Z" — is solved with dynamic programming where dp[i] equals dp[i-1] (if the single digit at i-1 is valid, 1-9) plus dp[i-2] (if the two digits ending at i-1 form a valid 10-26 code), computed in O(n) time and O(1) space.
At each position, a valid decoding either treats the current digit as a standalone letter code (valid only if the digit is 1-9, since "0" alone has no letter mapping) or combines it with the previous digit as a two-digit code (valid only if the two-digit number falls between 10 and 26 inclusive). Summing these two possibilities, when both are valid, gives the total decodings ending at that position, mirroring the same "current depends on previous one or two states" pattern as climbing stairs, but with validity conditions gating each term. The base cases require care: dp[0] = 1 represents the empty prefix, and a leading zero anywhere with no valid single or double interpretation collapses the count to zero for the rest of the string. This problem is a favorite because it looks like climbing stairs but the extra validity checks (especially handling "0" and combinations above 26) trip up candidates who pattern-match too quickly.
- O(n) time with a single left-to-right pass
- O(1) space using two rolling variables
- Reuses the "sum of previous one or two states" DP shape from climbing stairs
- Validity gating on digits (0, 10-26) is the key extra complexity over simpler counting DP
AI Mentor Explanation
Counting the number of ways to interpret a sequence of shot-signal digits sent from the dressing room, where a single digit maps to one shot code and a valid pair of digits maps to a different combined shot code, is the decode ways problem. At each signal, the batter either reads it as one standalone digit-code, valid only if it is not zero, or combines it with the previous digit into a two-digit code, valid only if that pairing falls in the recognized combined-code range. Summing the counts from both valid readings at each position gives the total number of ways the whole signal sequence could be interpreted. A zero digit that cannot stand alone and cannot complete a valid pair collapses the count to zero, exactly like an unreadable, ambiguous signal aborting the whole sequence.
Step-by-Step Explanation
Step 1
Define dp[i]
dp[i] = number of ways to decode the first i characters of the digit string.
Step 2
Add the single-digit case
If s[i-1] != "0", add dp[i-1] to dp[i], since that digit alone is a valid A-9 code.
Step 3
Add the two-digit case
If the two-digit number s[i-2:i] is between 10 and 26 inclusive, add dp[i-2] to dp[i].
Step 4
Seed base cases carefully
dp[0] = 1 (empty prefix); dp[1] = 1 if s[0] != "0" else 0, since a leading zero has no valid decoding.
What Interviewer Expects
- Correctly derive dp[i] = dp[i-1] (if valid single digit) + dp[i-2] (if valid two-digit pair)
- Handle "0" correctly — it is never a valid single-digit code and only valid as the second digit of 10 or 20
- Get the base cases right, including a leading zero producing zero total decodings
- Optimize from an O(n) array to O(1) rolling variables
Common Mistakes
- Treating "0" as if it maps to a letter, producing wrong counts
- Forgetting the two-digit range is 10-26 inclusive, not 1-26 or 11-26
- Not short-circuiting to zero when a "0" cannot be validly paired with the preceding digit
- Copying the climbing-stairs recurrence verbatim without adding the validity checks this problem requires
Best Answer (HR Friendly)
“Decode ways counts how many ways a string of digits can be decoded into letters, where 1 through 26 map to A through Z. I solve it with dynamic programming similar to climbing stairs, but at each position I only add the single-digit interpretation if that digit is not zero, and only add the two-digit interpretation if the pair falls between 10 and 26 — those validity checks are what make this problem trickier than plain step counting.”
Code Example
def num_decodings(s: str) -> int:
if not s or s[0] == "0":
return 0
prev2, prev1 = 1, 1 # dp[i-2], dp[i-1]
for i in range(1, len(s)):
current = 0
if s[i] != "0":
current += prev1
two_digit = int(s[i - 1:i + 1])
if 10 <= two_digit <= 26:
current += prev2
prev2, prev1 = prev1, current
return prev1
# num_decodings("226") -> 3 ("BZ", "VF", "BBF")Follow-up Questions
- How would you extend this to also decode a wildcard character "*" that could represent any digit?
- How would you modify the solution to return one valid decoded string instead of just the count?
- Why can dp[i] become 0 partway through the string, and what does that mean for the rest of the computation?
- How does this problem’s recurrence compare structurally to the climbing stairs problem?
MCQ Practice
1. Why can the digit "0" never be decoded as a standalone letter code?
The mapping is 1=A through 26=Z, so 0 has no single-digit letter mapping and is only valid as the second digit of 10 or 20.
2. What is the valid range for a two-digit decode in the decode ways problem?
A valid two-digit code must be between 10 and 26 inclusive, since those are the only two-digit letter mappings (J through Z, plus 10 for J).
3. What is the time and space complexity of the optimized decode ways solution?
A single left-to-right pass with two rolling variables gives O(n) time and O(1) space, avoiding a full dp array.
Flash Cards
What is the decode ways recurrence? — dp[i] = dp[i-1] (if s[i-1] != "0") + dp[i-2] (if s[i-2:i] is between 10 and 26).
Why is "0" a special case in decode ways? — It has no single-digit letter mapping, so it is only valid as the second digit of 10 or 20.
What base case must be handled carefully in decode ways? — A leading zero digit gives zero total decodings for the whole string.
How does decode ways relate to climbing stairs? — Same "sum of previous one or two states" DP shape, but gated by digit validity checks (nonzero single digit, 10-26 pair).