Easy C++ DP and recursive

• Here is my DP and Recursive solution with easy explanations

``````class Solution {
public:
// DP version
// dp[k] = dp[k-2] * parseDoubleChars(s[k-1],s[k]) + dp[k-1] * parseSingleChar(s[k])
int numDecodings(string s) {
long long int dp, dp1, dp2;
dp2 = parseSingleChar(s[0]); if (s.length()==1) return dp2;
dp1 = dp2 * parseSingleChar(s[1]) + parseDoubleChars(s[0],s[1]);
if (s.length()==2) return dp1;
for (int k = 2; k<s.length(); ++k){
dp = dp2 * parseDoubleChars(s[k-1],s[k]) + dp1 * parseSingleChar(s[k]);
dp %= 1000000007L;
dp2 = dp1;
dp1 = dp;
}
return dp;
}
int parseSingleChar(char c){
switch (c){
case '0':
return 0;
case '*':
return 9;
default:
return 1;
}
}
int parseDoubleChars(char c0, char c1){
int num = 0;
if (c0=='0' || c0>'2') return 0;
if (c0=='1' || c0=='*') num += c1=='*' ? 9 : 1;
if (c0=='2' || c0=='*') num += c1=='*' ? 6 : (c1>'6' ? 0 : 1);
return num;
}
};
/* recursive version, easy to understand but exceeds the time limit
class Solution{
public:
int numDecodings(string s) {
return numDecSubString(s, 0, 'n'); // 'n' means new start
}
int numDecSubString(string &s, int k, char prev){
long long int num = 0;
if (k>=s.size()) return 1; // terminate
// cout << k << " " << prev << s[k] << endl;
if (prev=='n'){ // new start
if (s[k]=='0') return 0;
num += (s[k]=='*' ? 9 : 1) * numDecSubString(s, k+1, 'n');
if (k==s.size()-1) return num;
if (s[k]=='1' || s[k]=='*') num += numDecSubString(s, k+1, '1');
if (s[k]=='2' || s[k]=='*') num += numDecSubString(s, k+1, '2');
}else if (prev=='1'){ // all is valid
num += (s[k]=='*' ? 9 : 1) * numDecSubString(s, k+1, 'n');
}else if (prev=='2'){
if (s[k]>'6') {return 0;}
else num += (s[k]=='*' ? 6 : 1) * numDecSubString(s, k+1, 'n');
}
return num % (1000000000L+7);
}
};
*/
``````

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