Sharing my C++ dp code


  • 0
    X
    //decode ways
    class Solution {
    public:
        int numDecodings(string s) {
            if (s.length() == 0) return 0;
            int n = s.length();
            vector<int> dp(n + 1, 0);
            dp[0] = 1; //  dp[0] = 1 is a trap
            dp[1] = 1;
            
            int i = 0;
            while (i < n && s[i] == '0') i++;
            
            if (i != 0) return 0;
            
            for (i = 2; i <= n; i++) {
                if (s[i-1] != '0') 
                    dp[i] += dp[i-1];
                
                if (stoi( s.substr(i-2, 2) ) >= 10 && stoi( s.substr(i-2, 2) ) <= 26)
                    dp[i] += dp[i-2];
            }
            
            return dp[n];
        }
    };

Log in to reply
 

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