# Java, straightforward solution, O(N) time, O(1) space

• First consider the 4 cases of the current character (*, 0, 1--6, 7--9) ;

Then consider the 4 cases of the previous character as sub-cases under each case (*, 1, 2, else);

``````public class Solution {
public int numDecodings(String s) {
int mod = 1_000_000_007;
if (s==null || s.length() ==0 || s.charAt(0)=='0') return 0;
long prevprev=1, prev= s.charAt(0) == '*' ? 9 : 1; //important! prevprev = 1 not 0, since it's valid; otherwise 1* will return 9 but not 18
for (int i=1; i<s.length(); i++){
long count =0; //to prevent overflow
char ch = s.charAt(i), prevCh = s.charAt(i-1);
if(ch == '0') {
if (prevCh == '1' || prevCh =='2') {
count = prevprev;
} else if (prevCh == '*') {
count = prevprev * 2;
} else {
return 0;
}
} else if (ch > '6' && ch != '*') {
count = prev;
if (prevCh == '1' || prevCh == '*') {
count += prevprev;
}
} else if (ch == '*') {
count = 9*prev;
if (prevCh =='1' || prevCh =='*') {
count += prevprev * 9;
}
if (prevCh =='2' || prevCh =='*') {
count += prevprev * 6; //* represent 1--6,  not  0--6
}
}  else {
count = prev;
if (prevCh == '1' || prevCh == '*') {
count += prevprev;
}
if (prevCh =='2' || prevCh =='*') {
count += prevprev;
}
}
prevprev = prev;
prev = count % mod;
}
return (int) prev;
}
}
``````

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