Approach Summary
dp[i] = ways to decode s[0..i). Single digit: valid if not "0". Two digits: valid if in 10-26 range.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: 1D Dynamic Programming Tabulation | O(n) | O(n) | Tabulate prefix decodings dp[i] checking valid single-digit (1-9) and two-digit (10-26) splits. |
| 2 Approach 2: Two-Variable Space Optimization (Optimal) | O(n) | O(1) | Track only the last two decoding counts in O(1) auxiliary space. |
Step 1: Baseline
Approach 1: 1D Dynamic Programming Tabulation
Time: O(n)
Space: O(n)
Construct array dp of size n + 1. dp[0] = 1 represents the empty string. dp[1] = 1 if s[0] != '0' else 0. Iterate i from 2 to n. Extract single-digit s[i-1]. If non-zero, add dp[i-1]. Extract two-digit s[i-2...i-1]. If between 10 and 26, add dp[i-2]. The result is dp[n].
Approach 1: 1D Dynamic Programming Tabulation Implementation
Approach 1: 1D Dynamic Programming Tabulation
class Solution {
public int numDecodings(String s) {
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = (s.charAt(0) != '0') ? 1 : 0;
for (int i = 2; i <= n; i++) {
int oneDigit = Integer.parseInt(s.substring(i - 1, i));
int twoDigits = Integer.parseInt(s.substring(i - 2, i));
if (oneDigit >= 1 && oneDigit <= 9) {
dp[i] = dp[i] + dp[i - 1];
}
if (twoDigits >= 10 && twoDigits <= 26) {
dp[i] = dp[i] + dp[i - 2];
}
}
return dp[n];
}
}class Solution {
public:
int numDecodings(string s) {
int n = s.size();
vector<int> dp(n + 1, 0);
dp[0] = 1;
dp[1] = (s[0] != '0') ? 1 : 0;
for (int i = 2; i <= n; i++) {
int oneDigit = stoi(s.substr(i - 1, 1));
int twoDigits = stoi(s.substr(i - 2, 2));
if (oneDigit >= 1 && oneDigit <= 9) {
dp[i] += dp[i - 1];
}
if (twoDigits >= 10 && twoDigits <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}
};class Solution:
def numDecodings(self, s: str) -> int:
if not s or s[0] == '0':
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
if s[i - 1] != '0':
dp[i] += dp[i - 1]
two_digit = int(s[i - 2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i - 2]
return dp[n]function numDecodings(s) {
if (!s || s[0] === '0') return 0;
const n = s.length;
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
const one = parseInt(s.substring(i - 1, i), 10);
const two = parseInt(s.substring(i - 2, i), 10);
if (one >= 1 && one <= 9) dp[i] += dp[i - 1];
if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
}
return dp[n];
} Step 2: Most Optimized
Approach 2: Two-Variable Space Optimization (Optimal)
Time: O(n)
Space: O(1)
Because dp[i] only looks back at dp[i - 1] and dp[i - 2], store them in variables prev2 and prev1. Update them on each character, discarding older counts to achieve constant space.
Approach 2: Two-Variable Space Optimization (Optimal) Implementation
Approach 2: Two-Variable Space Optimization (Optimal)
class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
int prev2 = 1, prev1 = 1;
for (int i = 1; i < s.length(); i++) {
int curr = 0;
int one = s.charAt(i) - '0';
int two = (s.charAt(i - 1) - '0') * 10 + one;
if (one >= 1) curr += prev1;
if (two >= 10 && two <= 26) curr += prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
}class Solution {
public:
int numDecodings(string s) {
if (s.empty() || s[0] == '0') return 0;
int prev2 = 1, prev1 = 1;
for (int i = 1; i < s.size(); i++) {
int curr = 0;
int one = s[i] - '0';
int two = (s[i - 1] - '0') * 10 + one;
if (one >= 1) curr += prev1;
if (two >= 10 && two <= 26) curr += prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
};class Solution:
def numDecodings(self, s: str) -> int:
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
two_digit = int(s[i - 1:i + 1])
if 10 <= two_digit <= 26:
curr += prev2
prev2 = prev1
prev1 = curr
return prev1function numDecodings(s) {
if (!s || s[0] === '0') return 0;
let prev2 = 1;
let prev1 = 1;
for (let i = 1; i < s.length; i++) {
let curr = 0;
const one = parseInt(s[i], 10);
const two = parseInt(s.substring(i - 1, i + 1), 10);
if (one >= 1) curr += prev1;
if (two >= 10 && two <= 26) curr += prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}Edge Cases to Watch
- Leading zero (e.g. "06"; cannot be decoded, returns 0)
- Invalid inner zero (e.g. "30"; 30 > 26 and '0' cannot stand alone, returns 0)
- Valid zeros (e.g. "10" or "20"; exactly 1 way to decode as 'J' or 'T')
- Consecutive 1s and 2s with branching choices (e.g. "226" -> "BZ", "VF", "BBF"; returns 3)
Algorithmic Pattern
View Pattern Guide →
Master the Dynamic Programming Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Dynamic Programming pattern.
Framework: Dynamic Programming • Interview Prep: Tested at FAANG •
Explore all Dynamic Programming problems & invariants →
How to Recognize This Pattern
- Number of ways to decode digit string
- Leading zero constraint
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
String DP
Frequently Asked Questions
What is the optimal time and space complexity for Decode Ways?
The optimal solution for Decode Ways achieves O(n) runtime complexity and requires O(1) auxiliary space. Time complexity is O(n) because we examine each character once and perform constant-time substring and range checks. Space complexity is O(n) for the 1D DP array, which can be optimized to O(1) space with two variables.
How do I identify that Decode Ways requires the Dynamic Programming pattern?
In technical interviews, look for key problem signals: Number of ways to decode digit string; Leading zero constraint. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Dynamic Programming strategy.
What critical edge cases must be handled in Decode Ways?
Essential edge cases to verify include: Leading zero (e.g. "06"; cannot be decoded, returns 0); Invalid inner zero (e.g. "30"; 30 > 26 and '0' cannot stand alone, returns 0); Valid zeros (e.g. "10" or "20"; exactly 1 way to decode as 'J' or 'T'); Consecutive 1s and 2s with branching choices (e.g. "226" -> "BZ", "VF", "BBF"; returns 3). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Decode Ways?
Decode Ways is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, Microsoft.