[639. Decode Ways II] C++_Dynamic Programming AC


  • 0
    class Solution {
    public:
    const int MOD = 1000000007;
    int numDecodings(string s) {
        if(s.empty()) return 0;
        long ptr0 = 1;
        long ptr1 = 0;
        if(s[0] == '*'){
            ptr1 = 9;
        }else if(s[0] -'0' != 0){
            ptr1 = 1;
        }
        for(int i = 1; i < s.size(); ++i){
            long sum = 0;
            //1 digit
            if(s[i] == '*'){
                sum = ptr1 * 9;//9 cases.
            }else if(s[i] - '0' != 0){
                sum = ptr1;
            }
            //2 digits
            if(s[i-1] != '*' && s[i] != '*'){
                int two = (s[i-1] - '0')*10 + s[i] - '0';
                if(two >= 10 && two <= 26) sum = sum + ptr0;
            }else if(s[i-1] != '*' && s[i] == '*'){//1*, 2*,·····
                int count = 0;
                for(int j = 1; j <= 9; ++j){
                    int tmp = (s[i-1] - '0') * 10 + j;
                    if(tmp <= 26 && tmp >= 10){count++;}
                    else{break;}
                }
                sum = sum + ptr0 * count;
            }else if(s[i-1] == '*' && s[i] != '*'){//*1,*2,····
                int count = 0;
                if(10 + (s[i] - '0') <= 26) count++;
                if(20 + (s[i] - '0') <= 26) count++;
                sum = sum + ptr0 * count;
            }else{//s[i] == '*' && s[i-1] == '*', "**"
               sum = sum + ptr0 * 15;//11,12,13,14,15,16,17,18,19,21,22,23,24,25,26
            }
            ptr0 = ptr1%MOD;
            ptr1 = sum%MOD;
        }
        return ptr1 % MOD;
    }
    };

Log in to reply
 

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