## # 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) {
int count = 0;
count += doNumDecodings(s, head + 1);
if (head < s.size() - 1 &&
count += doNumDecodings(s, head + 2);
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;
}
};
``````