🎉 One-stop destination for all your technical interview Preparation 🎉
A message containing letters from A-Z can be encoded into numbers using the following mapping:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, “11106” can be mapped into:
Note that the grouping (1 11 06) is invalid because “06” cannot be mapped into ‘F’ since “6” is different from “06”. Given a string s containing only digits, return the number of ways to decode it. The test cases are generated so that the answer fits in a 32-bit integer.
way1+way2
because we want to find all the possible ways to decode the string.class Solution {
private:
int numDecodingsRec(string& s, int i)
{
int n = s.size();
if (i == n) return 1;
if (s[i] == '0') return 0;
int way1 = numDecodingsRec(s, i + 1), way2 = 0;
if (i < n - 1 && stoi(s.substr(i, 2)) <= 26)
way2 = numDecodingsRec(s, i + 2);
return way1 + way2;
}
public:
int numDecodings(string s)
{
if (s.empty()) return 0;
return numDecodingsRec(s, 0);
}
};
class Solution {
private:
int dp[101];
int numDecodingsRec(string& s, int i)
{
int n = s.size();
if (i == n) return 1;
if (s[i] == '0') return 0;
if (dp[i] != -1) // if we have already calculated the result, return it.
return dp[i];
int way1 = numDecodingsRec(s, i + 1), way2 = 0;
if (i < n - 1 && stoi(s.substr(i, 2)) <= 26)
way2 = numDecodingsRec(s, i + 2);
return dp[i] = way1 + way2; // store the result in the memoization table.
}
public:
int numDecodings(string s)
{
if (s.empty()) return 0;
memset(dp, -1, sizeof(dp));
return numDecodingsRec(s, 0);
}
};
class Solution {
public:
int numDecodings(string s)
{
int n = s.size();
if (n == 0)
return 0;
vector<int> dp(n + 1);
dp[n] = 1;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == '0')
dp[i] = 0;
else {
dp[i] = dp[i + 1];
// The second condition is to check if the string is 1[*] or 2[1-6].
if (i < n - 1 && (s[i] == '1' || (s[i] == '2' && s[i + 1] < '7')))
dp[i] += dp[i + 2];
}
}
return dp[0];
}
};