MediumNeetCode150StringDynamic Programming
Decode Ways
Count ways to decode numeric string to letters.
Examples
Input
s = "226"
Output
3
BZ(2,26), VF(22,6), BB(2,2,6).
Constraints
- •
1 <= s.length <= 100 - •
s consists of digits, no leading zeros
Approaches
Try 1 or 2 digits.
CodeT: O(2^n) | S: O(n) stack
dp[i] = ways to decode s[:i].
CodeT: O(n) | S: O(n)
dp[i] depends on dp[i-1] and dp[i-2].
CodeT: O(n) | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursion | O(2^n) | O(n) stack | Try 1 or 2 digits. |
| DP 1D | O(n) | O(n) | dp[i] = ways to decode s[:i]. |
| DP Two Variables | O(n) | O(1) | dp[i] depends on dp[i-1] and dp[i-2]. |
Recursion
T: O(2^n)S: O(n) stack
Try 1 or 2 digits.
DP 1D
T: O(n)S: O(n)
dp[i] = ways to decode s[:i].
DP Two Variables
T: O(n)S: O(1)
dp[i] depends on dp[i-1] and dp[i-2].
Common Mistakes
Not handling leading zeros
Off-by-one
Not checking valid range [1-26]