1. Problem Summary
You’re given a digit string s that encodes letters using the mapping:
"1" → 'A', "2" → 'B', …, "26" → 'Z'.
You can decode the string by grouping 1 or 2 digits at a time, as long as:
A single digit is valid if it’s from "1" to "9".
A two-digit number is valid if it’s from "10" to "26".
Anything with leading zeroes like "06" is invalid.
Task: Return the number of different valid ways to decode the entire string. If it’s impossible, return 0.
Constraints:
1 <= s.length <= 100
s contains only digits '0'–'9'
May contain leading zero(s)
2. Examples Explanation
Example 1:
Input: s = "12"
Output: 2
Valid decodings:
"1" "2" → "A" "B" → "AB"
"12" → "L"
So there are 2 ways.
Example 2:
Input: s = "226"
Output: 3
Valid decodings:
"2" "26" → "B" "Z" → "BZ"
"22" "6" → "V" "F" → "VF"
"2" "2" "6" → "B" "B" "F" → "BBF"
Total 3 ways.
Example 3:
Input: s = "06"
Output: 0
"06" is not valid due to leading '0'.
"0" alone is not valid. No valid decomposition, so result is 0.
3. Approach
Pattern:
This is a classic Dynamic Programming (DP) problem on a string, very similar to counting the number of ways to climb stairs with constraints, where each step depends on the previous one or two steps.
Naive / Brute-force Idea:
Use DFS/backtracking:
At each index, either:
Take one digit (if valid), or
Take two digits (if valid),
Recursively count all ways.
This leads to exponential time in the worst case, roughly O(2n).
Optimal Idea: DP (1D, bottom-up):
High-Level Idea:
Let:
dp[i] = number of ways to decode the prefix s[0..i-1] (first i characters).
We want dp[n] where n = len(s).
Transitions (for i from 1 to n):
One-digit decode (last 1 char):
Let one = s[i-1] (as a single digit).
If one is between '1' and '9', then we can append this single decoded character to any decoding of s[0..i-2]:
So, dp[i] += dp[i-1].
Two-digit decode (last 2 chars):
If i >= 2:
Let two = s[i-2..i-1] (two characters).
If two is between "10" and "26" (no leading zero, valid mapping), then we can append this decoded character to any decoding of s[0..i-3]:
So, dp[i] += dp[i-2].
Initial conditions:
dp[0] = 1 (empty string has exactly one way to decode: do nothing)
If s[0] == '0', then dp[1] = 0 (invalid), otherwise dp[1] = 1.
Important zero rules:
'0' cannot stand alone.
Valid two-digit combinations involving '0': only "10" and "20".
Key Observations:
The number of ways at position i only depends on i-1 and i-2 ⇒ we can optimize space to O(1).
If at any point both:
The single digit s[i-1] is '0', and
The two-digit s[i-2..i-1] is not in [10, 26],
then decoding is impossible ⇒ result is 0.
Space Optimization:
Instead of using an entire array:
Use two variables:
prev = dp[i-1]
prev2 = dp[i-2]
Compute current = ways using one-digit + ways using two-digit, then update:
prev2 = prev
prev = current
This keeps memory O(1).
Pseudo-code:
Complexity Analysis:
Time Complexity:
We iterate once over the string, doing O(1) work per index.
Total: O(n) where n = len(s).
Space Complexity:
With space optimization, we only keep a few integers (prev, prev2, current).
Total: O(1) extra space.
4. Java code
5. C code
6. C++ code
7. Python code
8. JavaScript code
Comments
Post a Comment