# 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;
    }
};