Python, Straightforward with Explanation


  • 38
    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. : )


  • 2
    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


  • 2

    After solving nearly 600 problems on leetcode, I still can't write elegant code like this by myself.

    java version

    public int numDecodings(String s) {
            long mod = (long)Math.pow(10, 9) + 7l;
            long endingAny = 1, ending1 = 0, ending2 = 0;
            for (char c: s.toCharArray()) {
                long curEndingAny = 0;
                if (c == '*') {
                    curEndingAny = 9 * endingAny + 9 * ending1 + 6 * ending2;
                    ending1 = endingAny;
                    ending2 = endingAny;
                } else {
                    curEndingAny = (c == '0'? 0:endingAny) + ending1 + (c <= '6'? ending2:0);
                    ending1 = (c == '1'? endingAny:0);
                    ending2 = (c == '2'? endingAny:0);
                }
                endingAny = curEndingAny % mod;
            }
            return (int)endingAny;
        }
    

  • 0
    W

    Just have one question confusing me since I touched this problem: why there are 6 ways when ending on an open 2. I feel like 2 can be followed by 0 to 6, which would 7 ways instead of 6. What did I miss please?

    Thanks for the help!


  • 0
    M

    @WXBigBear Remember that * can only be numbers between 1 and 9, not 0. So if you have an open 2, then the possible second digit numbers are between 1 and 6.


  • 0
    P
    This post is deleted!

Log in to reply
 

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