# Java DP solution and recursive solution.

• ``````public int numDecodings(String s) {
if(s.length() == 0) return 0;
int n = s.length();
int[] A = new int[n+1];
A[n] = 1;
A[n-1] = s.charAt(n-1) == '0'?0:1;
for(int i=n-2;i>=0;i--){
if(s.charAt(i) != '0'){
A[i] = A[i+1];
int val = Integer.parseInt(s.substring(i,i+2));
if(val > 0 && val <=26){
A[i] += A[i+2];
}
}
}
return A[0];
}
``````

use recursion

``````HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
public int numDecodings(String s) {
if(s.length() == 0) return 0;
return decode(s,0);
}
public int decode(String s,int i){
if(i == s.length()) return 1;
if(i == s.length()-1) return s.charAt(i) == '0'?0:1;
if(map.containsKey(i)) return map.get(i);
if(s.charAt(i) =='0') return 0;
int res = decode(s,i+1);
int val = Integer.parseInt(s.substring(i,i+2));
if(val > 0 && val <=26){
res += decode(s,i+2);
}
map.put(i,res);
return res;
}``````

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