Sharing another dp solutions.


  • 0
    A

    Validity can simply be checked by using the fact that character cannot be '0' to be valid for both single and double digits.

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

Log in to reply
 

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