Here's a long and easy solution for reference


  • 6
    V
    int numDecodings(string s) {
        if(s.size() == 0 || s[0] == '0')
            return 0;
        int len = s.size();
        vector<int> dp(len+1, 0);
        dp[0] = dp[1] = 1;
        for(int i=2; i<=len; i++){
            int a = s[i-2] - '0';
            int b = s[i-1] - '0';
            if(a == 0 && b == 0)
                return 0;
            if(a == 0 && b != 0){
                dp[i] = dp[i-1];
                continue;
            }
            if(a != 0 && b == 0){
                if(a > 2)
                    return 0;
                else{
                    dp[i] = dp[i-2];
                    continue;
                }
            }
            int temp = a * 10 + b;
            if(temp > 26)
                dp[i] = dp[i-1];
            else
                dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[len];
    }

Log in to reply
 

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