c++ dp solution


  • 0
    B

    note the situation when s[i]=='0'

    class Solution {
    public:
        int numDecodings(string s) {
            vector<int> dp(s.length()+1,1);     // s[i] maps to dp[i+1];
            if(!s.length() || s[0]=='0') return 0;
            
            for(int i=1;i<s.length();i++){
                int num=(s[i-1]-'0')*10+(s[i]-'0');
                if(s[i]=='0'){
                    if(s[i-1]!='1' && s[i-1]!='2') return 0;
                    else dp[i+1]=dp[i-1];
                }
                else if(10<num && num<27) dp[i+1]=dp[i-1]+dp[i];
                    else dp[i+1]=dp[i];
            }
            return dp[s.length()];
        }
    };
    

Log in to reply
 

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