Straight forward C++ AC solution, DP


  • 0
    F
    int numDecodings(string s) {
        int n = s.size();
        if(n < 1) return 0;
        vector<long> dp(n+1, 0);     
        dp[0] = 1;
        if(s[0] == '*'){
            dp[1] = 9;
        }else if(s[0] - '0' > 0){ 
            dp[1] = 1;
        }
        int base;
        base = 1000000000 + 7;
        int single; // number of ways using 1 digit
        int Double; // number of ways using 2 digits
        for(int i = 2; i <= n; i++){
            if(isdigit(s[i-1])){ // current position is a number
                single = 1;
                Double = 0;
                if(s[i-1] - '0' == 0){
                    single = 0;
                }
                if(isdigit(s[i-2])){
                    if(s[i-2] - '0' > 0){
                        int val = (s[i-2] - '0') * 10 + s[i-1] -'0';
                        if(val <= 26){ 
                            Double = 1;
                        }
                    }
                }else{
                    int val = s[i-1] - '0';
                    if(val <= 6){
                        Double = 2;
                    }else{
                        Double = 1;
                    }
                }
                dp[i] = ((dp[i-1] * single) % base + (dp[i-2] * Double) % base) % base ;
            }else{
                single = 9;
                Double = 0;
                if(isdigit(s[i-2])){
                    if(s[i-2] - '0' == 0){
                        Double = 0;
                    }else if(s[i-2] - '0' == 1){
                        Double = 9;
                    }else if(s[i-2] - '0' == 2){
                        Double = 6;
                    }else{
                        Double = 0;
                    }
                }else{
                    Double = 9 + 6;
                }
                dp[i] = ((dp[i-1] * single) % base + (dp[i-2] * Double) % base) % base ;
            }
        }
        return dp[n];
    }

Log in to reply
 

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