# Lookup table, DP O(n) runtime and O(1) space

• ``````public class Solution {
static final Map<String, Integer> map2 = new HashMap<>();
static {
map2.put("**", 15);
map2.put("*0", 2);
map2.put("*1", 2);
map2.put("*2", 2);
map2.put("*3", 2);
map2.put("*4", 2);
map2.put("*5", 2);
map2.put("*6", 2);
map2.put("1*", 9);
map2.put("2*", 6);
map2.put("27", 0);
map2.put("28", 0);
map2.put("29", 0);
}
static final Map<Character, Integer> map1 = new HashMap<>();
static {
map1.put('*', 9);
map1.put('0', 0);
}
public int numDecodings(String s) {
int n = s.length();
s = s + "0";
long cur = 0, pre1 = 1, pre2 = 0;
for (int i = n - 1; i >= 0; i--) {
char ch = s.charAt(i);

cur = map1.getOrDefault(ch, 1) * pre1;
if (ch == '*' || ch == '1' || ch == '2') {
cur += map2.getOrDefault(s.substring(i, i+2), 1) * pre2;
}
cur %= 1000000007;
pre2 = pre1;
pre1 = cur;
}

return (int) cur;
}
}
``````

Or, even shorter:

``````public class Solution {
static final int[][] map = new int[58][58];
static {
Arrays.fill(map['*'], 1);
map['*']['*'] = 15;
map['*']['0'] = 2;
map['*']['1'] = 2;
map['*']['2'] = 2;
map['*']['3'] = 2;
map['*']['4'] = 2;
map['*']['5'] = 2;
map['*']['6'] = 2;
Arrays.fill(map['1'], 1);
map['1']['*'] = 9;
Arrays.fill(map['2'], 1);
map['2']['*'] = 6;
map['2']['7'] = 0;
map['2']['8'] = 0;
map['2']['9'] = 0;
Arrays.fill(map[0], 1);
map[0]['*'] = 9;
map[0]['0'] = 0;
}

public int numDecodings(String s) {
long cur = 1, pre = 0;
char ch = 0, ch1 = '0';
for (int i = s.length() - 1; i >= 0; i--) {
ch = s.charAt(i);
cur = (map[ch][ch1] * pre + map[0][(ch1 = ch)] * (pre = cur)) % 1000000007;
}

return (int) cur;
}
}
``````

• @tyuan73 I basically had same idea, but in recursion + memorization. But the call stack is too long for memory if input `s` is huge...

``````    int numDecodings(string s) {
if (s.empty()) return 0;
memo = vector<int>(s.size(), -1);
return ways(s);
}

long ways(string s, int i = 0) {
if (i == s.size()) return 1;
if (i > s.size()) return 0;
if (memo[i] >= 0) return memo[i];
if (s[i] == '0') return 0;

long res = 0;
if (s[i] == '*') {
res = (9*ways(s, i+1))%MOD;
if (i+1 < s.size()) {
if (s[i+1] == '*') (res += 15L*ways(s, i+2)) %= MOD;
else if (s[i+1] - '6' > 0) (res += ways(s, i+2)) %= MOD;
else (res += 2L*ways(s, i+2)) %= MOD;
}
}
else {
res = ways(s, i+1);
if (i+1 < s.size()) {
if (s[i] == '1') {
if (s[i+1] == '*') (res += 9L*ways(s, i+2)) %= MOD;
else (res += ways(s, i+2)) %= MOD;
}
else if (s[i] == '2') {
if (s[i+1] == '*') (res += 6L*ways(s, i+2)) %= MOD;
else if (s[i+1] - '7' < 0) (res += ways(s, i+2)) %= MOD;
}
}
}
return memo[i] = res;

}

const int MOD = 1000000007;
vector<int> memo;
``````

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