C++ O(N) runtime O(N) space


  • 0
    G
    class Solution {
    public:
        
        #define MOD(x) ((x) % 1000000007)
        
        int numDecodings(string s) {
            if(s.empty()){
                return 0;
            }
            
            vector<long long> D(s.size() + 1,0);
            D[0] = 1;
            
            for(int i = 1; i <= s.size(); ++i){
                if(s[i - 1] != '*'){
                    
                    if(s[i - 1] != '0'){
                        D[i] = D[i - 1];
                    }
                    
                    if(i >= 2){
                        if((s[i - 2] == '1' && s[i - 1] >= '0' && s[i - 1] <= '9') ||
                            s[i - 2] == '2' && s[i - 1] >= '0' && s[i - 1] <= '6'){
                            D[i] = MOD(D[i] + D[i - 2]);
                        }
                        else if(s[i - 2] == '*'){
                            D[i] = MOD(D[i] + D[i - 2] + (s[i - 1] <= '6' ? D[i - 2] : 0));
                        }
                    }
                }
                else{
                    D[i] = MOD(9*D[i - 1]);
                    
                    if(i >= 2){
                        if(s[i - 2] == '*' || s[i - 2] == '1'){
                            D[i] = MOD(D[i] + MOD(9*(D[i - 2])));
                        }
                    
                        if(s[i - 2] == '*' || s[i - 2] == '2'){
                            D[i] =  MOD(D[i] + MOD(6*(D[i - 2])));
                        }
                    }
                }
            }
            
            return D[s.size()];
        }
    };
    

Log in to reply
 

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