C++ 4ms Solution using DP


  • -1
    H
    class Solution {
    public:
    int numDecodings(string s) {
        int size = s.size();
        if(size == 0 || s[0] == '0'){
            return 0;
        }
        if(size == 1 && s[0] != '0'){
            return 1;
        }
        vector<int> dp(size,0);
        if(s[0]!='0'){
            dp[0] = 1;
        }
        if(s[1]!='0'){
            dp[1] = 1;
          
        }
    
    
        if(s[0] == '1'){
            dp[1] += 1;
            
        }else if(s[0] =='2' && s[1] < '7' ){
            dp[1] += 1;
            
        }
       
        for(int i = 2; i<size;i++){
            if(s[i] > '0' && s[i-1]>='0' && s[i-1] <='9'){
                dp[i] +=dp[i-1];
             
            }
            if(s[i-1] == '1' || (s[i-1] == '2' && s[i] >='0'&& s[i] < '7' )){
                dp[i] += dp[i-2];
                
            }
           
            
        }
        return dp[size-1];
    }
    };

Log in to reply
 

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