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 an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Solution:

class Solution {
public:
    int numDecodings(string s) {
        vector<int> ans(s.size() + 1);
        if (s.size() == 0 || s[0] == '0') {
            return 0;
        }
        if (s.size() == 1)
            return 1;
        ans[0] = 1, ans[1] = 1;
        int tmp = s[0];
        for (int i = 2; i <= s.size(); i++) {
            if (s[i - 1] == '0') {
                if (s[i - 2] == '1' || s[i - 2] == '2') {
                    ans[i] = ans[i - 2];
                    continue;
                } else {
                    return 0;
                }
            }
            tmp = s[i - 2] - '0';
            if (tmp == 0) {
                // case: 101
                ans[i] = ans[i - 1];
                continue;
            }
            tmp = tmp * 10 + (s[i - 1] - '0');
            if (tmp > 26) {
                ans[i] = ans[i - 1];
            } else {  // case: 1 to 26: exception already included above i.e. 10 and 20.
                ans[i] = ans[i - 1] + ans[i - 2];
            }
        }
        return ans[s.size()];
    }

// ==== Recursive === not clean one ====
    /*int decod(string s, int l, int r) {
        if (s[l] == '0')
            return 0;
        if (r == 0)
            return r;
        if (r - l == 1) {
            if (s[r - 1] == '0')
                return 0;
            return 1;
        } else if (r - l == 2) {
            if ((s[l] == '1' || s[l] == '2') && s[l + 1] == '0') {
                return 1;
            } else if (s[l] == '1' ||
                       s[l] == '2' && s[l+1] <= '6' && s[l+1] >= '0') {
                return 2;
            } else if (s[l] == '0' || s[l + 1] == '0') {
                return 0;
            } else {
                return 1;
            }
        } else {
            if ((s[r - 2] == '1' || s[r - 2] == '2') && s[r - 1] == '0') {
                return decod(s, l, r - 2);
            } else if (s[r - 2] == '1' ||
                      (s[r - 2] == '2' && s[r - 1] <= '6' && s[r - 1] >= '0')) {
                return decod(s, l, r - 2) + decod(s, l, r - 1);
            } else if (s[r - 1] == '0' ||
                       (s[r - 2] == '0' && s[r-3] != '2' && s[r-3] != '1')) {
                return 0;
            } else {
                return decod(s, l, r - 1);
            }
        }
    }*/
};


============ Another attempt ======
==== Recursive and DP solutions (bottom-up, top-bottom)=======

class Solution {
public:
int numDecodings(string s) {
        // Recursive.
        // return helper(s, 0);
     
        // Dynamic programming (top bottom)
        //vector<int> dp(s.size() + 1, -1);
        //return helper_dynamic(s, 0, dp);
     
     
        // Bottom up DP. Give solution according to string length.
        vector<int> dp;
        dp.push_back(1);   // zero length string.
        if (s[0] == '0') {
            return 0;
        }
        dp.push_back(1);  // As first character is non zero.
     
        for (int i = 1; i < s.size(); i++) {
            int ans = 0;
            int cur_digit = (s[i] - '0');
            int prev_digit = (s[i - 1] - '0');
            if (cur_digit != 0) {
                ans = dp[i];         // last solution stored in dp.
            }
            int combined_digit = (prev_digit * 10) + cur_digit;
            if (combined_digit > 9 && combined_digit < 27) {
                ans += dp[i - 1];    // last to last solution stored in dp.
            }
         
          /* // Not needed by the way.
            if (ans == 0) {
                return 0;   // that means something like 100 occurred.
            }
         */
            dp.push_back(ans);    // dp[i + 1] = ans;    // can't do as vector element is not allocated.
        }
        return dp[s.size()];
    }





    /* //   Top Bottom Dynamic
    int helper_dynamic(string s, int start, vector<int>& dp) {
        // End of the array.
        if (start == s.size()) {
            return 1;
        }
        // First element 0.
        if (s[start] == '0') {
            return 0;
        }
        // Just one non zero element.
        if (s.size() - start == 1) {
            return 1;
        }
        int ans;
        if (dp[start + 1] != -1) {
            ans = dp[start + 1];
        } else {
            ans = helper_dynamic(s, start + 1, dp);
            dp[start + 1] = ans;
        }

        int num = (s[start] - '0') * 10 + (s[start + 1] - '0');
        if (num > 9 && num <= 26) {
            if (dp[start + 2] != -1) {
                ans += dp[start + 2];
            } else {
                ans += helper_dynamic(s, start + 2, dp);
                dp[start + 2] = ans;
            }
        }
     
        return ans;
    }
    */
 
// Recursive.
    /*
        ans = {s[0].decode(s[1..n]) + s[0,1].decode(s[2..n])}
        i.e. ans = (first element & remaining sols) +
                    (first two element & remaining sols)
    */
    /*
    int helper(string s, int start) {
        // End of the array.
        if (start == s.size()) {
            return 1;
        }
        // First element 0.
        if (s[start] == '0') {
            return 0;
        }
        // Just one non zero element.
        if (s.size() - start == 1) {
            return 1;
        }
     
        int ans = helper(s, start + 1);
        int num = (s[start] - '0') * 10 + (s[start + 1] - '0');
        if (num > 9 && num <= 26) {
            ans += helper(s, start + 2);
        }
     
        return ans;
    }
    */
};

===================== Another attempt ======
int numDecodings(string s) { if (s.size() == 0 || s[0] == '0') { return 0; } vector<int> dp(s.size() + 1, 0); dp[0] = 1; dp[1] = 1; for (int i = 1; i < s.size(); i++) { if (s[i] != '0') { dp[i + 1] += dp[i]; } int val = (s[i - 1] - '0') * 10 + (s[i] - '0'); if (val >= 10 && val <= 26) { dp[i + 1] += dp[i - 1]; } if (val == 0) { return 0; } } return dp[s.size()]; }