#include <iostream>
#include <string>
#include <vector>
using namespace std;
int numDecodings(string);
int numDecodings_dp_iterative(string);
int numDecodings_dp_optimised(string);
int main() {
string input_str = "123123";
cout << "Number of ways (recursive algorithm): " << numDecodings(input_str) << endl;
cout << "Number of ways (dynamic programming): " << numDecodings_dp_iterative(input_str) << endl;
cout << "Number of ways (optimised dynamic programming): " << numDecodings_dp_optimised(input_str) << endl;
return 0;
}
int numDecodings(string s) {
int len = s.length();
// Base cases
if (len == 0) {
return 1;
}
if (s[0] == '0') {
return 0;
}
// Recursive steps
if (len >= 2 && atoi(s.substr(0, 2).c_str()) <= 26) {
return numDecodings(s.substr(1, len-1)) +
numDecodings(s.substr(2, len-2));
}
else {
return numDecodings(s.substr(1, len-1));
}
}
int numDecodings_dp_iterative(string s) {
int i = 0, len = s.length();
vector<int> num_ways(len+1, 0); // num_ways[i] will hold the possibilities for the string s[:i]
// Takes care of the base case when s="" is supplied
if (len > 0)
num_ways[i++] = 1;
while (i <= len) {
// If a valid pair is present at the beginning of the current substring
if (i >= 2 && s[i-2] != '0' && atoi(s.substr(i-2, 2).c_str()) <= 26) {
num_ways[i] += num_ways[i-2];
}
// If a valid digit is present at the beginning of the current substring
if (i >= 1 && s[i-1] != '0') {
num_ways[i] += num_ways[i-1];
}
i++;
}
return num_ways[len]; // num_ways[len] will hold the result
}
int numDecodings_dp_optimised(string s) {
int i = 0, len = s.length ();
int m = 0, n = 0, temp;
// Takes care of the base case when s="" is supplied
if (len > 0)
m = 1;
while (i < len) {
temp = 0; // using temp for num_ways[i]
if (i >= 1 && s[i-1] != '0' && atoi (s.substr (i-1, 2).c_str ()) <= 26){
temp += n; // using n for num_ways[i-2]
}
if (i >= 0 && s[i] != '0') {
temp += m; // using m for num_ways[i-1]
}
/* When i is incremented, num_ways[i-1] becomes num_ways[i-2] and
num_ways[i] becomes num_ways[i-1] */
i++;
n = m;
m = temp;
}
return m;
}
