91. Decode Ways - cocoder39/coco39_LC GitHub Wiki

int numDecodings(string s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }
        vector<int> dp(len + 1); //dp[i] is numDecodings of s[0 ... i - 1]
        dp[0] = 1;
        
        for (int i = 1; i <= len; i++) {
            int singleDig = s[i - 1] != '0' ? dp[i - 1] : 0;
            int doubleDig = i >= 2 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] >= '0' && s[i- 1] <= '6')) ? dp[i - 2] : 0;
            dp[i] = singleDig + doubleDig;
        }
        return dp[len];
    }

int numDecodings(string s) {
        int len = s.length();
        if (len == 0) {
            return 0;
        }
        
        int pre1 = 1, pre2;
        for (int i = 1; i <= len; i++) {
            int singleDig = s[i - 1] != '0' ? pre1 : 0;
            int doubleDig = i >= 2 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] >= '0' && s[i- 1] <= '6')) ? pre2 : 0;
            
            pre2 = pre1;
            pre1 = singleDig + doubleDig;
        }
        return pre1;
    }

int numDecodings(string s) {
        if (s.empty())  return 0;
        
        int res = 0;
        if (s[0] >= '1' && s[0] <= '9') {
            res += s.length() > 1 ? numDecodings(s.substr(1)) : 1;
        }
        if (s.length() > 1 && (s[0] == '1' || (s[0] == '2' && s[1] >= '0' && s[1] <= '6'))) {
            res += s.length() > 2 ? numDecodings(s.substr(2)) : 1;
        }
        return res;
    }

#include <vector>

using namespace std;

void helper(vector<vector<string>>& res, vector<string>& cur, string& s, int start) {
    if (start == s.length()) {
        res.push_back(cur);
        return;
    }

    if (s[start] >= '1' && s[start] <= '9') {
        cur.push_back(string(1, s[start]));
        helper(res, cur, s, start + 1);
        cur.pop_back();
    }
    if (start + 1 < s.length() && (s[start] == '1' || (s[start] == '2' && s[start + 1] >= '0' && s[start + 1] <= '6'))) {
        cur.push_back(s.substr(start, 2));
        helper(res, cur, s, start + 2);
        cur.pop_back();
    }
}

void decode(string& s) {
    vector<vector<string>> res;
    vector<string> cur;
    helper(res, cur, s, 0);

    for (auto &strs : res) {
        for (auto &str : strs) {
            cout << str << " ";
        }
        cout << endl;
    }
}

int main() {
    string str("10223456");
    decode(str);
    return 0;
}