# 91. Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
# Solution
Approach 1: DP (front to back, or back to front)
# Code (Python)
Approach 1:
def numDecodings(self, s: str) -> int:
if len(s) == 0:
return 0
if len(s) == 1:
return 0 if s == '0' else 1
if s.startswith('0') or (s[1] == '0' and int(s[0]) > 2) or "00" in s:
return 0
window = (1, 1) if s[1] == '0' or int(s[:2]) > 26 else (1, 2)
for i in range(2, len(s)):
if s[i] == '0':
if int(s[i-1]) > 2:
return 0
num_decodings = window[0]
else:
if int(s[i-1:i+1]) > 26:
num_decodings = window[1]
else:
if s[i-1] == '0':
num_decodings = window[1]
else:
num_decodings = window[0] + window[1]
window = (window[1], num_decodings)
return window[-1]
# Code (C++)
Approach 1:
class Solution {
private:
vector<int> memo;
int doNumDecodings(string s, int head) {
if (memo[head] >= 0)
return memo[head];
int count = 0;
if (s[head] > '0')
count += doNumDecodings(s, head + 1);
if (head < s.size() - 1 &&
(s[head] == '1' || s[head] == '2' && s[head+1] <= '6'))
count += doNumDecodings(s, head + 2);
memo[head] = count;
return count;
}
public:
int numDecodings(string s) {
memo = vector<int>(s.size() + 1, -1);
memo[s.size()] = 1;
return doNumDecodings(s, 0);
}
};
class Solution {
public:
int numDecodings(string s) {
int counts[s.size()+1] = {0};
counts[s.size()] = 1;
for (int i = s.size() - 1; i >= 0; --i)
{
if (s[i] > '0')
counts[i] += counts[i+1];
if (i < s.size() - 1 &&
(s[i] == '1' || s[i] == '2' && s[i+1] <= '6'))
counts[i] += counts[i+2];
}
return counts[0];
}
};
class Solution {
public:
int numDecodings(string s) {
int bypass1 = 1;
int bypass2 = 1;
for (int i = s.size() - 1; i >= 0; --i)
{
int count = 0;
if (s[i] > '0')
count += bypass1;
if (i < s.size() - 1 &&
(s[i] == '1' || s[i] == '2' && s[i+1] <= '6'))
count += bypass2;
bypass2 = bypass1;
bypass1 = count;
}
return bypass1;
}
};
class Solution {
public:
int numDecodings(string s) {
int prevCount = 1;
int prevPrevCount = 1;
for (int i = 0; i < s.size(); ++i)
{
int count = 0;
if (s[i] >= '1')
count += prevCount;
if (i > 0 && (s[i-1] == '1' || s[i-1] == '2' && s[i] <= '6'))
count += prevPrevCount;
prevPrevCount = prevCount;
prevCount = count;
}
return prevCount;
}
};