my c++ dp solution


  • 0
    C
    class Solution {
    public:
        int numDecodings(string s) {
            int n = s.size();
            if (n == 0 || s[0] == '0') return 0; // some bad case
            vector<int> dp(n + 1, 1);
            for (int i = 2; i <= n; ++i) {
                int cur = s[i - 1] - '0', pre = s[i - 2] - '0';
                if (cur == 0) { // if cur is 0, it must combine with the pre, it can not be alone
                    if (pre == 0 || pre > 2) return 0; // here is the illegal combine
                    dp[i] = dp[i - 2]; //if it is legal, it does not add any combination
                } else {
                    dp[i] = dp[i - 1]; // be alone
                    int two = pre * 10 + cur; // combine with the pre
                    if (two <= 26 && pre != 0) dp[i] += dp[i - 2]; // if it is legal combine, it add a combination
                }
            }
            return dp[n];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.