My C++ DP code with runtime at 5ms


  • 2
    M
    int numDecodings(string s){
        if(s.length() == 0) return 0;
    
        if(s.length() == 1) return s[0]=='0'?0:1;
    
        vector<int>dp(s.length()+1,0);
        dp[s.length()] = 1;
        dp[s.length()-1] = (s[s.length()-1] == '0')?0:1;
        for(int i = s.length()-2; i >= 0 ; i--)
        {
            if (s[i] != '0'){
                
                dp[i] += dp[i+1];
                
                if (((s[i]-'0') *10+s[i+1]-'0') <= 26 )
                    dp[i] += dp[i+2];
            }
        }
        return dp[0];
    }

Log in to reply
 

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