Decode Ways
Asked at Google, Meta, Amazon, Microsoft, Apple, Uber, Walmart
Problem
A message consisting of letters is encoded into numbers using the mapping A=1, B=2, ..., Z=26. Given a string of digits s, return the number of ways to decode it.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Uber | Medium | View all Uber questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Similar to climbing stairs: at each position, you can take 1 digit or 2 digits (if valid). The difference is that not all choices are valid.
dp[i] = dp[i-1] (if single digit s[i-1] is valid, i.e., not 0) + dp[i-2] (if two digits s[i-2:i] form 10-26).
A single digit is valid if it's 1-9 (not 0). A two-digit number is valid if it's 10-26 (not 00, 01-09, 27-99).
Space optimization: use two variables instead of an array, same as climbing stairs.
Visual walkthrough for s="226":
dp[0]=1, dp[1]=1 (s[0]="2" is valid)
i=2: single "2" valid → +dp[1]=1. "22" valid (10-26) → +dp[0]=1. dp[2]=2.
i=3: single "6" valid → +dp[2]=2. "26" valid (10-26) → +dp[1]=1. dp[3]=3.
Result: 3 ways: "2 2 6", "22 6", "2 26".
Edge cases: leading zeros (return 0), single digit (1 if valid), digits > 26 at the end.
Optimal Approach
Step 1: If s is empty or starts with 0, return 0.
Step 2: Initialize prev2 = 1, prev1 = 1.
Step 3: For i from 1 to len(s)-1:
curr = 0
If s[i] != '0': curr += prev1 (single digit valid)
If 10 <= int(s[i-1:i+1]) <= 26: curr += prev2 (two digits valid)
prev2, prev1 = prev1, curr
Step 4: Return prev1.
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Confusing this with "count distinct substrings." This is about counting valid decodings, not substrings.
Not handling zeros correctly. A single 0 is invalid (can't decode). A 0 after a 1 or 2 is valid (10 or 20), but a 0 after anything else is invalid.
Forgetting that two-digit numbers must be 10-26. Numbers like 27-99 can't be decoded as two digits.
Not handling the edge case of an empty string. Return 0, not 1.
Using an O(n) dp array when O(1) space with two variables is possible. Each position only depends on the previous two values — optimize space with two variables.
Solution Code
def numDecodings(s):
if not s or s[0] == '0':
return 0
prev2, prev1 = 1, 1
for i in range(1, len(s)):
curr = 0
if s[i] != '0':
curr += prev1
if 10 <= int(s[i-1:i+1]) <= 26:
curr += prev2
prev2, prev1 = prev1, curr
return prev1Frequently Asked Questions
What is the Decode Ways problem?
A message consisting of letters is encoded into numbers using the mapping `A=1`, `B=2`, ..., `Z=26`. Given a string of digits s, return the number of ways to decode it.
How do you solve Decode Ways?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Decode Ways?
Decode Ways is asked at Google, Meta, Amazon, Microsoft, Apple, Uber, Walmart. It is a medium difficulty problem.
What are common mistakes on Decode Ways?
- Confusing this with "count distinct substrings." This is about counting valid decodings, not substrings.
- Not handling zeros correctly. A single 0 is invalid (can't decode). A 0 after a 1 or 2 is valid (10 or 20), but a 0 after anything else is invalid.
- Forgetting that two-digit numbers must be 10-26. Numbers like 27-99 can't be decoded as two digits.
- Not handling the edge case of an empty string. Return 0, not 1.
- Using an `O(n)` dp array when `O(1)` space with two variables is possible. Each position only depends on the previous two values — optimize space with two variables.