# Java DP Solution O(n) time and space, Some Explanations

• Take "1*" as an example. It can be "11"-"19". You can read it into "A" and "A" to "A" and "I" or you can treat it as a two digit number as "K" to "S". That is the way you decode the code.
So if you treat the current character s.charAt(i) as a single character, the dp result of the index i should be the number of choices of current character times dp[i-1]. If you put the s.charAt(i) together with s.charAt(i-1) as a two digit number (if possible, something like "29" is not a possible pair), dp[i] should add the choices of the current pair times dp[i-2]. That is basic thinking of dp for this problem. Then what should be done is to find what kind of pairs or single numbers are valid. Like a single "0" is not valid, and there is no answer for something like "30".
Just think about the different conditions carefully.

``````public int numDecodings(String s) {
int len = s.length();
int mod = 1000000007;
long [] dp = new long[len + 1];
dp[0] = 1;
if (s.charAt(0) == '0') return 0;
if (s.charAt(0) == '*'){
dp[1] = 9;
}
else{
dp[1] = 1;
}
for (int i = 2; i<=len; i++) { // i-1 the index of current character in s.
if (s.charAt(i-1) == '0') {
if (s.charAt(i-2) == '1' || s.charAt(i -2) == '2') {
dp[i] = dp[i-2];
}
else if(s.charAt(i-2) == '*'){
dp[i] = 2*dp[i-2];
}
else {
return 0;
}
}
else if(s.charAt(i-1) >= '1' && s.charAt(i-1) <= '9') {
dp[i] = dp[i-1];
if (s.charAt(i-2) == '1' || (s.charAt(i-2) == '2' && s.charAt(i-1) <= '6') ){
dp[i] = (dp[i] + dp[i-2]) % mod;
}
else if (s.charAt(i-2) == '*') {
if (s.charAt (i-1) <= '6') {
dp[i] = (dp[i] + dp[i-2] * 2) % mod;
}
else {
dp[i] = (dp[i] + dp[i-2]) % mod;
}
}
}
else { //s.charAt(i-1) == '*'
dp[i] = (9*dp[i-1]) % mod;
if ( s.charAt(i-2) == '1' ){ // 11 - 19
dp[i] = ( dp[i] + 9 * dp[i-2] ) % mod;
}
else if (s.charAt(i-2) == '2') { // 21 - 26
dp[i] = ( dp[i] + 6 * dp[i-2] ) % mod;
}
else if (s.charAt(i - 2) == '*') {
dp[i] = ( dp[i] + 15 * dp[i-2] ) % mod;
}
}
}
return (int)dp[len];
}``````

• Similar ideas in Python

``````class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
N = len(s)
dp = [0] * (N + 1)
dp[N] = 1
dp[N - 1] = 9 if s[N - 1] == '*' else 0 if s[N - 1] == '0' else 1
for i in range(N - 2, -1, -1):
if s[i] == '0':
continue
if s[i] == '*':
dp[i] += 9 * dp[i + 1]
if s[i + 1] == '*':
dp[i] += 15 * dp[i + 2]
elif int(s[i + 1]) <= 6:
dp[i] += 2 * dp[i + 2]
else:
dp[i] += dp[i + 2]
else:
dp[i] += dp[i + 1]
if s[i + 1] == '*':
if s[i] == '1':
dp[i] += 9 * dp[i + 2]
elif s[i] == '2':
dp[i] += 6 * dp[i + 2]
else:
if int(s[i:i + 2]) <= 26:
dp[i] += dp[i + 2]
dp[i] %= 1000000007
return dp[0]
``````

• why do you need to take modulus of 1000000007 ?

• @rcholic It is required by the problem.

• Brilliant idea! But why for `s.charAt(i-1) == '*' && s.charAt(i-2) == '*'` the transition function is `dp[i] = (dp[i] + 15 * dp[i-2]) % mod` rather than `dp[i] = (dp[i] + 16 * dp[i-2]) % mod` ? I think I can not figure out why we should consider `s.charAt(i-1) == '0'` as a new situation (my wrong solution only discussed `s.charAt(i-1) == '*'` and `s.charAt(i-1) != '*'`). Thx!

• @Chen_Xiang
Because ''*" represents 1 to 9 as it is said in the question. I used to make the same mistake.
And also u need think about the substrings like "0*", it is not a valid substring to represent any alphabet.

• @Nakanu Thx!

• @Chen_Xiang Ah, I just noticed the asterisk was used for the html format... Now it is correct...

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