My 3ms C++ DP solution


  • 0
    G

    I think that deal with the problem from head to tail is easier to understand.

    class Solution {
    public:
        int numDecodings(string s) {
            int size = s.size();
            if(size == 0 || s[0] == '0')
                return 0;
            else if(size == 1)
                return 1;
            
            int res[size + 1] = {0};
            res[0] = 1;
            res[1] = s[1] == '0' ? 0 : 1;
            
            for(int i = 2; i <= size; ++i)
            {
                if(i < size && s[i] == '0')
                    res[i] = 0;
                else if(s.substr(i - 2, 2) <= "26")
                    res[i] = res[i - 1] + res[i - 2];
                else
                    res[i] = res[i - 1];
            }
            
            return res[size];
        }
    };
    

Log in to reply
 

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