@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;