# Backtracking HashMap based solution (14 ms) as well as DP solution (5 ms). Easy to understand. Good read.

• ``````public int numDecodings(String s) {// Dynamic programming way! Tedious one.
if (s.length() < 1)
return 0;
int DP[] = new int[s.length() + 1];
DP[0] = 1; // Initialization
DP[1] = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= s.length(); i++) {
String str = s.substring(i - 2, i); // last two digit number
int val2 = Integer.valueOf(str);
int val1 = s.charAt(i - 1) - '0'; // last 1 digit number

if (val1 > 0)
DP[i] += DP[i - 1];
if (val2 >= 10 && val2 <= 26) // tricky part.
DP[i] += DP[i - 2];
}

return DP[s.length()];

}
``````

Backtracking based solution using HashMap:

``````
public int numDecodings(String s) { // Inefficient backtracking solution. But works flawlessely!
if (s.length() == 0)
return 0;
Map<String, Integer> map = new HashMap<>();
return numDecodings(s, map);
}

public int numDecodings(String s, Map<String, Integer> map) {
if (s.length() == 0)
return 1;
int res = 0;
for (int i = 0; i < s.length(); i++) { // Will run twice basically. What the heck I was thinking ?
int val = Integer.valueOf(s.substring(0, i + 1));
if (val <= 26 && val > 0) {
if (map.containsKey(s)) {
return map.get(s);
}
res += numDecodings(s.substring(i + 1, s.length()), map);
} else
break;
}
map.put(s, res);
return res;
}
``````

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