# Straight forward C++ AC solution, DP

• ``````int numDecodings(string s) {
int n = s.size();
if(n < 1) return 0;
vector<long> dp(n+1, 0);
dp[0] = 1;
if(s[0] == '*'){
dp[1] = 9;
}else if(s[0] - '0' > 0){
dp[1] = 1;
}
int base;
base = 1000000000 + 7;
int single; // number of ways using 1 digit
int Double; // number of ways using 2 digits
for(int i = 2; i <= n; i++){
if(isdigit(s[i-1])){ // current position is a number
single = 1;
Double = 0;
if(s[i-1] - '0' == 0){
single = 0;
}
if(isdigit(s[i-2])){
if(s[i-2] - '0' > 0){
int val = (s[i-2] - '0') * 10 + s[i-1] -'0';
if(val <= 26){
Double = 1;
}
}
}else{
int val = s[i-1] - '0';
if(val <= 6){
Double = 2;
}else{
Double = 1;
}
}
dp[i] = ((dp[i-1] * single) % base + (dp[i-2] * Double) % base) % base ;
}else{
single = 9;
Double = 0;
if(isdigit(s[i-2])){
if(s[i-2] - '0' == 0){
Double = 0;
}else if(s[i-2] - '0' == 1){
Double = 9;
}else if(s[i-2] - '0' == 2){
Double = 6;
}else{
Double = 0;
}
}else{
Double = 9 + 6;
}
dp[i] = ((dp[i-1] * single) % base + (dp[i-2] * Double) % base) % base ;
}
}
return dp[n];
}``````

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