Decode Ways
You're given a string s of digits. It encodes a message of uppercase letters where A was written as "1", B as "2", and so on up to Z as "26", with all the codes joined together and no separators. Return the number of ways to split s back into letters. Every piece must be a number from 1 to 26 written without a leading zero, so neither "0" nor "06" is a valid piece. Return 0 if s can't be decoded at all.
Examples
s = "12" returns 2
Split it as 1 2 ("AB") or keep 12 together ("L").
s = "226" returns 3
The three splits are 2 2 6 ("BBF"), 22 6 ("VF") and 2 26 ("BZ").
s = "06" returns 0
The first piece would have to start with 0, and neither "0" nor "06" maps to a letter, so there is no valid decoding.
Constraints
- 1 <= s.length <= 100
- s contains only digits and may contain leading zero(s).
- The answer fits in a 32-bit integer.
Hints
Think about the last letter of any valid decoding. It came from either the last one digit or the last two digits of s.
Dynamic programming over prefixes: ways[i] = the number of decodings of s[:i]. It's a staircase where some steps are broken.
Set ways[0] = 1. For each i, add ways[i-1] if s[i-1] is not '0', and add ways[i-2] if s[i-2..i-1] is between 10 and 26. Return ways[n]; two rolling variables are enough.
Drill This: Your Approach First
Approach
Let ways[i] be the number of decodings of the first i characters, with ways[0] = 1 for the empty prefix. The last piece of a prefix is either one digit, valid when it isn't '0' (add ways[i-1]), or two digits, valid when they form 10 to 26 (add ways[i-2]). Each step reads only the previous two counts, so two rolling variables are enough. O(n) time, O(1) space.
Time
O(n)
Space
O(1)
Pitfall
Solutions
class Solution {
public int numDecodings(String s) {
int prev2 = 1; // ways to decode the first i - 2 chars
int prev1 = s.charAt(0) == '0' ? 0 : 1; // ways to decode the first i - 1 chars
for (int i = 2; i <= s.length(); i++) {
int cur = 0;
if (s.charAt(i - 1) != '0') cur += prev1;
int two = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
if (two >= 10 && two <= 26) cur += prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}class Solution:
def numDecodings(self, s: str) -> int:
prev2 = 1 # ways to decode s[:i - 2]
prev1 = 0 if s[0] == "0" else 1 # ways to decode s[:i - 1]
for i in range(2, len(s) + 1):
cur = 0
if s[i - 1] != "0":
cur += prev1
if 10 <= int(s[i - 2:i]) <= 26:
cur += prev2
prev2, prev1 = prev1, cur
return prev1