# Evolve from recursion to dp

1. Recursion O(2^n)
``````    int numDecodings(string s) {
return s.empty() ? 0: numDecodings(0,s);
}
int numDecodings(int p, string& s) {
int n = s.size();
if(p == n) return 1;
if(s[p] == '0') return 0;
int res = numDecodings(p+1,s);
if( p < n-1 && (s[p]=='1'|| (s[p]=='2'&& s[p+1]<'7'))) res += numDecodings(p+2,s);
return res;
}
``````
1. Memoization O(n)
``````    int numDecodings(string s) {
int n = s.size();
vector<int> mem(n+1,-1);
mem[n]=1;
return s.empty()? 0 : num(0,s,mem);
}
int num(int i, string &s, vector<int> &mem) {
if(mem[i]>-1) return mem[i];
if(s[i]=='0') return mem[i] = 0;
int res = num(i+1,s,mem);
if(i<s.size()-1 && (s[i]=='1'||s[i]=='2'&&s[i+1]<'7')) res+=num(i+2,s,mem);
return mem[i] = res;
}
``````
1. dp O(n) time and space, this can be converted from #2 with copy and paste.
``````    int numDecodings(string s) {
int n = s.size();
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];
if(i<n-1 && (s[i]=='1'||s[i]=='2'&&s[i+1]<'7')) dp[i]+=dp[i+2];
}
}
return s.empty()? 0 : dp[0];
}
``````
1. dp constant space
``````    int numDecodings(string s) {
int p = 1, pp, n = s.size();
for(int i=n-1;i>=0;i--) {
int cur = s[i]=='0' ? 0 : p;
if(i<n-1 && (s[i]=='1'||s[i]=='2'&&s[i+1]<'7')) cur+=pp;
pp = p;
p = cur;
}
return s.empty()? 0 : p;
}
``````

• Implementing your idea in Java, I think this should be top 1 post, if we show our thinking process like this, we could get a strong hire estimation in the interview.
#2 Memoization O(n), #2 in Java doesn't pass LC's time complexity check since LC probably has more restrict requirements for Java, but I test the code in eclipse and it's correct.

``````public int numDecodings(String s) {
if(s == null || s.length() == 0) return 0;
HashMap<Integer, Integer> map = new HashMap<>();
return dfs(s, map, 0);
}

public int dfs(String str, HashMap<Integer, Integer> map, int index){
if(index == str.length()){
return 1;
}
if(map.containsKey(index)) {
return map.get(index);
}
if(str.charAt(index) == '0') {
map.put(index, 0);
return 0;
}
int res = dfs(str, map, index + 1);
if(index + 1 < str.length() && (str.charAt(index) == '1' || (str.charAt(index) == '2' && str.charAt(index + 1) < '7'))){
res += dfs(str, map ,index + 2);
}
return res;
}
``````

#3 dp O(n) time and space

``````public int numDecodings(String s) {
if(s == null || s.length() == 0) return 0;
int n = s.length();
int [] dp = new int [n + 1];
dp[n] = 1;
for(int i = n - 1; i >= 0; i--) {
if(s.charAt(i) == '0'){
dp[i] = 0;
}else{
dp[i] = dp[i + 1];
if(i + 1 < s.length() && (s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i + 1) < '7'))){
dp[i] += dp[i + 2];
}
}
}
return dp[0];
}
``````

#4 dp constant space

``````public int numDecodings(String s) {
if(s == null || s.length() == 0) return 0;
int n = s.length();
int pp = 0;
int p = 1;
for(int i = n - 1; i >= 0; i--) {
int cur = s.charAt(i) == '0' ? 0 : p;
if(i + 1 < s.length() && (s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i + 1) < '7'))){
cur += pp;
}
pp = p;
p = cur;
}
return p;
}
``````

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