Python, Straightforward with Explanation


  • 17
    def numDecodings(self, S):
        MOD = 10**9 + 7
        e0, e1, e2 = 1, 0, 0
        for c in S:
            if c == '*':
                f0 = 9*e0 + 9*e1 + 6*e2
                f1 = e0
                f2 = e0
            else:
                f0 = (c > '0') * e0 + e1 + (c <= '6') * e2
                f1 = (c == '1') * e0
                f2 = (c == '2') * e0
            e0, e1, e2 = f0 % MOD, f1, f2
        return e0
    

    Let's keep track of:

    • e0 = current number of ways we could decode, ending on any number;
    • e1 = current number of ways we could decode, ending on an open 1;
    • e2 = current number of ways we could decode, ending on an open 2;

    (Here, an "open 1" means a 1 that may later be used as the first digit of a 2 digit number, because it has not been used in a previous 2 digit number.)

    With the right idea of what to keep track of, our dp proceeds straightforwardly.


    Say we see some character c. We want to calculate f0, f1, f2, the corresponding versions of e0, e1, e2 after parsing character c.

    If c == '*', then the number of ways to finish in total is: we could put * as a single digit number (9*e0), or we could pair * as a 2 digit number 1* in 9*e1 ways, or we could pair * as a 2 digit number 2* in 6*e2 ways. The number of ways to finish with an open 1 (or 2) is just e0.

    If c != '*', then the number of ways to finish in total is: we could put c as a single digit if it is not zero ((c>'0')*e0), or we could pair c with our open 1, or we could pair c with our open 2 if it is 6 or less ((c<='6')*e2). The number of ways to finish with an open 1 (or 2) is e0 iff c == '1' (or c == '2').


  • 0

    @awice

    Great solution. : )


  • 0
    Z

    Thank you very much. I tried recursion with memoization in the contest, but got TLE, and my code was quite long. After reading your solution, I realized that recursion is not necessary, this problem can be solved within O(1) space by quite short code


  • 1
    Z

    I just figured out a very complex and ugly solution, yours is very nice and clean, thank you very much.

    translate it to C++:

    class Solution {
    public:
        int numDecodings(string s) {
            long e0 = 1, e1 = 0, e2 = 0, f0, f1, f2;
            for ( char c : s ) {
                if ( '*' == c ) {
                    f0 = 9 * e0 + 9 * e1 + 6 * e2;
                    f1 = f2 = e0;
                } else {
                    f0 = int(c > '0') * e0 + e1 + int(c < '7') * e2;
                    f1 = '1' == c ? e0 : 0;
                    f2 = '2' == c ? e0 : 0;
                }
                e0 = f0 % 1000000007;
                e1 = f1;
                e2 = f2;
            }
            return int(e0);
        }
    };
    

  • 0
    I

    Simple and clean!!!
    very inspirational


Log in to reply
 

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