[C++] 15 lines, O(1) space, O(n) time, readable.


  • 1
    S
    • "" and strings start with '0' are properly handled.
    • tricky part: initial value of i, j, k, pre.

    int numDecodings(string s) {
        int i, j = 1, k = 0;
        char pre = '3'; // any except '1' and '2'
        for (char cur : s) {
            k = 0;
            if (cur > '0') // decode 1 digit
                k += j;
            if (pre == '1' || (pre == '2' && cur <= '6')) // decode 2 digits
                k += i;
            if (k == 0) // prune
                break;
            i = j;
            j = k;
            pre = cur;
        }
        return k;
    }

  • 0
    Z

    nice solution,thank you


Log in to reply
 

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