O(1) space, O(n) time DP


  • 0
    F
    class Solution {
    public:
        bool isWord(char a, char b)
        {
            return !(a < '1' || a >= '3' || (a == '2' && b > '6'));
        }
        int numDecodings(string s) {
            int dp = 0, i1 = 1, i2 = 1;
            for (int i = 0; i < s.size(); ++i)
            {
                dp = 0;
                if (s[i] != '0')
                    dp += i1;
                if (i > 0 && isWord(s[i-1], s[i]))
                    dp+= i2;
                i2 = i1;
                i1 = dp;
            }
            return dp;
        }
    };

Log in to reply
 

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