# Python, Straightforward with Explanation

• ``````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'`).

• @awice

Great solution. : )

• 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

• 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);
}
};
``````

• Simple and clean!!!
very inspirational

• 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;
}
``````

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

• @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.

• This post is deleted!

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