This is a straightforward dynamic programming question. Define dp[i] as the total number of ways to decode string of length i. Clearly, dp[0] = 0. Now, when we are considering a string of length i, we can either consider the last digit alone (ONLY if it is not 0 as 0 does not map to anything) or we can consider the last two digits. Let’s see these cases:
- Last digit is 0: we have to consider the second last and last digit together (making either 10 or 20) and there is no other way to decode so dp[i] = dp[i-2]
- Last digit is not 0:
- Consider the last digit alone. dp[i] += dp[i-1]
- Consider the last two digits. If they make a number <= 26 then dp[i] += dp[i-2]
class Solution {
public:
// define dp[i] as total number of ways to decode string of length i
// if the last digit is 0, then we have to consider the second last and last digit together (making either 10 or 20) and there is no other way to decode dp[i] = dp[i-2]
// if the last digit is not 0, we can consider it to be an independent digit (1 to 9 -> A to I) OR we may pair it up with the second last digit and decode it (only if second last digit and last digit are in the valid range, i.e., >=10 and <=26). So dp[i] = dp[i-1] + dp[i-2] if valid range else dp[i] = dp[i-1] (interpreted only as single digit => A to I)
int numDecodings(string s) {
int len = s.length();
if (!len)
return 0;
if (s[0] == '0')
return 0;
vector<int> dp(len+1, 0);
dp[0] = 1;
dp[1] = 1;
bool flag;
for (int i=2; i<len+1; i++) {
flag = false;
if (s[i-1] != '0')
dp[i] = dp[i-1];
string s1 = s.substr(i-2, 2);
if (stoi(s1) >= 10 && stoi(s1) <= 26)
dp[i] += dp[i-2];
}
return dp[len];
}
};
Time complexity: O(n) Space complexity: O(n)