C++ DP solution


  • 1
    G
    class Solution {
    public:
        int numDecodings(string s) 
        {
            vector<int> D(s.size(),0);
            
            if(s.empty())
            {
                return (0);
            }
            
            D[0] = (s[0] >= '1' && s[0] <= '9');
            
            for(int i = 1; i < D.size();++i)
            {
                D[i] = (s[i] >= '1' && s[i] <= '9' ? D[i - 1] : 0);
                
                if((s[i - 1] == '1' && s[i] >= '0' && s[i] <= '9') ||
                    (s[i - 1] == '2' && s[i] >= '0' && s[i] <= '6'))
                {
                    D[i] += (i > 1 ? D[i - 2] : 1);
                }
            }
            
            return (D[s.size() - 1]);
        }
    };

Log in to reply
 

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