# C++, DP, O(n) time O(1) space

• The idea is DP. One of the hints is that you need mod the answer with a huge prime number.

1. For any string s longer than 2, we can decode either the last 2 characters as a whole or the last 1 character. So dp[i] = dp[i-1]* f(s.substr(i,1)) + dp[i-2]* f(s.substr(i-1, 2)). f() is the number of ways to decode a string of length 1 or 2. f() could be 0, for example f("67").
2. There is a lot of cases and corner cases for f(string s). For example, * cannot be '0', so ** has 15 instead of 16 possibilities, because "20" is excluded. But the time complexity is still O(n).
The code is as below.
``````class Solution {
public:
int numDecodings(string s) {
int n = s.size(), p = 1000000007;
// f2 is the answer to sub string ending at position i; Initially i = 0.
long f1 = 1, f2 = helper(s.substr(0,1));
// DP to get f2 for sub string ending at position n-1;
for (int i = 1; i < n; i++) {
long f3 = (f2*helper(s.substr(i, 1)))+(f1*helper(s.substr(i-1, 2)));
f1 = f2;
f2 = f3%p;
}
return f2;
}
private:
int helper(string s) {
if (s.size() == 1) {
if (s[0] == '*') return 9;
return s[0] == '0'? 0:1;
}
// 11-26, except 20 because '*' is 1-9
if (s == "**")
return 15;
else if (s[1] =='*') {
if (s[0] =='1') return 9;
return s[0] == '2'? 6:0;
}
else if (s[0] == '*')
return s[1] <= '6'? 2:1;
else
// if two digits, it has to be in [10 26]; no leading 0
return stoi(s) >= 10 && stoi(s) <= 26? 1:0;
}
};
``````

• Nice solution. But how about s[0] = *, s[1] = 0(the string *0)? I think your program is going to output 2. I think it should be 1.

• @mgh
s = "*0" can be decoded into "10" or "20". It's 2

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