c++ dp solution

  • 0

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

    class Solution {
        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-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.