Easy C++ DP and recursive


  • 0
    M

    Here is my DP and Recursive solution with easy explanations

    class Solution {
    public:
        // DP version
        // dp[k] = dp[k-2] * parseDoubleChars(s[k-1],s[k]) + dp[k-1] * parseSingleChar(s[k])
        int numDecodings(string s) {
            long long int dp, dp1, dp2;
            dp2 = parseSingleChar(s[0]); if (s.length()==1) return dp2;
            dp1 = dp2 * parseSingleChar(s[1]) + parseDoubleChars(s[0],s[1]); 
            if (s.length()==2) return dp1;
            for (int k = 2; k<s.length(); ++k){
                dp = dp2 * parseDoubleChars(s[k-1],s[k]) + dp1 * parseSingleChar(s[k]);
                dp %= 1000000007L;
                dp2 = dp1; 
                dp1 = dp;
            }
            return dp;
        }    
        int parseSingleChar(char c){
            switch (c){
                case '0':
                    return 0;
                case '*':
                    return 9;
                default:
                    return 1;
            }
        }
        int parseDoubleChars(char c0, char c1){
            int num = 0;
            if (c0=='0' || c0>'2') return 0;
            if (c0=='1' || c0=='*') num += c1=='*' ? 9 : 1;
            if (c0=='2' || c0=='*') num += c1=='*' ? 6 : (c1>'6' ? 0 : 1);
            return num;
        }
    };
    /* recursive version, easy to understand but exceeds the time limit
    class Solution{
    public:
        int numDecodings(string s) {
            return numDecSubString(s, 0, 'n'); // 'n' means new start
        }
        int numDecSubString(string &s, int k, char prev){
            long long int num = 0;
            if (k>=s.size()) return 1; // terminate
            // cout << k << " " << prev << s[k] << endl;
            if (prev=='n'){ // new start 
                if (s[k]=='0') return 0;
                num += (s[k]=='*' ? 9 : 1) * numDecSubString(s, k+1, 'n');
                if (k==s.size()-1) return num;
                if (s[k]=='1' || s[k]=='*') num += numDecSubString(s, k+1, '1');
                if (s[k]=='2' || s[k]=='*') num += numDecSubString(s, k+1, '2');
            }else if (prev=='1'){ // all is valid
                num += (s[k]=='*' ? 9 : 1) * numDecSubString(s, k+1, 'n');
            }else if (prev=='2'){
                if (s[k]>'6') {return 0;}
                else num += (s[k]=='*' ? 6 : 1) * numDecSubString(s, k+1, 'n');
            }
            return num % (1000000000L+7);
        }    
    };
    */
    

Log in to reply
 

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