C++ Clear Logic with Comments. O(n) Time, O(1) Space.


  • 0
    F

    Don't be terrified by the if-else statements. I purposely didn't compress any logic to make the logic super clear and easy to follow. If you just read it, you will see my point. It is actually clearer than man

    class Solution {
        int base = 1000000007;
    public:
        int numDecodings(string s) {
            //last1: decode ways of s ending at i-1, last2 decode ways of s ending at i-2, nlast1 : next last1.
            long long last1 = 1, last2 = 1, nlast1 = 0; //there is only 1 way to decode "", so initialized with 1.
            for (int i = 0; i < s.size(); ++ i)
            {
                //Just look at current character
                if (s[i] == '*') 
                    nlast1 = last1 * 9 % base;
                else if (s[i] == '0')
                    nlast1 = 0;
                else
                    nlast1 = last1;
                //All three if below: look at last two characters.
                if (i > 0 && s[i - 1] == '1')
                    if (s[i] == '*')
                        nlast1 = (nlast1 + last2 * 9) % base;
                    else 
                        nlast1 = (nlast1 + last2) % base;
                if (i > 0 && s[i - 1] == '2')
                    if (s[i] == '*')
                        nlast1 = (nlast1 + last2 * 6) % base;
                    else if (s[i] <= '6')
                        nlast1 = (nlast1 + last2) % base;
                if (i > 0 && s[i - 1] == '*')
                    if (s[i] == '*')
                        nlast1 = (nlast1 + last2 * 15) % base; //1* + 2* = 15
                    else if (s[i] <= '6')
                        nlast1 = (nlast1 + last2 * 2) % base; //1a + 2a = 2, a is one fixed number.
                    else
                        nlast1 = (nlast1 + last2) % base; //1a = 1 case
                last2 = last1;
                last1 = nlast1;
            }
            return last1;
        }
    };
    

Log in to reply
 

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