# Java DP

• The difference of this problem compared with Decode Ways is that coefficient is no longer 1, we need to consider '*'. When calculate the possible combination of s[i-1, i], I consider following 4 situations:

1. s[i-1] = number, s[i] = number
2. s[i-1] = number, s[i] = *
3. s[i-1] = *, s[i] = number
4. s[i-1] = *, s[i] = *

DP function is:

``````dp[i+1] = one*dp[i] + two*dp[i-1]
``````
``````        int n = s.length();
if(n == 0) return 0;
if(s.charAt(0) == '0') return 0;

long[] dp = new long[n + 1];
dp[0] = 1;
dp[1] = s.charAt(0) == '*' ? 9 : 1;
int mod = 1000000007;

for(int i = 1; i < n; i++) {
int one = s.charAt(i) == '*' ? 9 : (s.charAt(i) == '0' ? 0 : 1);
dp[i+1] = (dp[i] % mod * one) % mod;

char last = s.charAt(i-1);
if((last != '*' && last > '2') || last == '0') continue;
char cur = s.charAt(i);
int two = 0;
if(cur != '*' && last != '*') {
if(last == '2' && cur > '6') two = 0;
else two = 1;
}
else if(cur != '*') {
if(cur > '6') two = 1; else two = 2;
}
else if(last != '*') {
if(last == '1') two = 9;
else two = 6;
}
else two = 15;
dp[i+1] = (dp[i+1] + dp[i-1] % mod * two) % mod;

}
return (int) dp[n];
``````

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