A clear DP solution with c++


  • 0
    H

    dp[i] is the number of decode ways by string s[1 .. n-1].

    class Solution {
    public:
        int numDecodings(string s) {
            const int len = s.length();
            if(len == 0) return 0;
            int dp[len] = {0};
            dp[0] = 1;
            dp[1] = s[0]=='0'?0:1;
            for(int i = 2; i <= len; i++){
                int lasttwo = 10*(s[i-2]-'0') + s[i-1] - '0';
                if(lasttwo >= 10 && lasttwo <= 26){
                    if(s[i-1] == '0') dp[i] = dp[i-2];
                    else dp[i] = dp[i-1] + dp[i-2];
                }else{
                    
                    if(s[i-1] == '0') dp[i] = 0;
                    else dp[i] = dp[i-1];
                }
            }
            return dp[len];
        }
    };

Log in to reply
 

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