Decode Ways
DFS Approach
Intuition
From left to right, we discover following rules:
- one word : can be
1~9 - two word : can be
1, 0~9and2, 0~6 - force two word :
1or2, 0 - lonely
0returns0.
Apply rules into DFS function.
Code
cpp
int numDecodings(string s) {
return dfs(s,0);
}
int dfs(string s, int i) {
if(i == s.size())return 1;
if(i > s.size())return 0;
if(s[i] == '0') return 0;
int res = 0;
res += dfs(s,i+1);
if(s[i] == '1' || s[i] == '2')
if(i+1 < s.size()) {
if(s[i] == '1')
res += dfs(s,i+2);
else if(s[i+1] < '7')
res += dfs(s,i+2);
}
return res;
}Complexity Analysis
Time: O(2^n)Space: O(1)
Memoization + DFS
Intuition
We can see there's many repeated work done in dfs function. To make for every i we only call dfs(s, i) once, we can cache the result of dfs(s,i) for every i, in a vector<int>memo.
Code
cpp
vector<int> memo;
int numDecodings(string s) {
memo.resize(s.size()+2, -1);
return dfs(s,0);
}
int dfs(string s, int i) {
if(i == s.size())return 1;
if(i > s.size())return 0;
if(s[i] == '0') return 0;
int res = 0;
res += (memo[i+1] != -1) ? memo[i+1] : memo[i+1] = dfs(s,i+1);
if(s[i] == '1' || s[i] == '2')
if(i+1 < s.size()) {
if(s[i] == '1')
res += (memo[i+2] != -1) ? memo[i+2] : memo[i+2] = dfs(s,i+2);
else if(s[i+1] < '7')
res += (memo[i+2] != -1) ? memo[i+2] : memo[i+2] = dfs(s,i+2);
}
return res;
}Complexity Analysis
Time: O(n)Space: O(n)
Dynamic Programming
Intuition
Since in DFS function we only request dfs(s,j), which j > i, so we can pre-calculate back values, by using buttom-up dp.
so, dp[i] = numDecoding(s.substr(i,s.size()-i)).
Code
cpp
int numDecodings(string s) {
vector<int> dp(s.size()+2, 0);
dp[s.size()] = 1;
for (int i = s.size()-1; i >= 0; --i) {
dp[i] += dp[i+1];
if(s[i] == '1')
dp[i] += dp[i+2];
else if(s[i] == '2' && i+1 < s.size() && s[i+1] < '7')
dp[i] += dp[i+2];
else if(s[i] == '0')
dp[i] = 0;
}
return dp[0];
}Complexity Analysis
Time: O(n)Space: O(n)