My C++ solution with O(1) space and O(n) time


  • 0
    S
    class Solution {
    public:
        int numDecodings(string s) {
            
            if(s.size() == 0)
                return 0;
                
            vector<int> m(3, 0);
            m[0] = 1;
            for(int i = 1; i <= s.size(); i++)
            {
                m[i%3] = 0;
                if(s[i-1] >= '1' && s[i-1] <= '9')
                    m[i%3] += m[(i-1)%3];
                if(i > 1)
                {
                    string twos = s.substr(i-2, 2);
                    int num = stoi(twos);
                    if(num >= 1 && num <= 26 && s[i-2] >= '1' && s[i-2] <= '2' && s[i-1] >= '0' && s[i-1] <= '9')
                    {
                        m[i%3] += m[(i-2)%3];
                    }
                }
            }
            return m[s.size()%3];
        }
    };

Log in to reply
 

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