Sharing my java memoized solution

• ``````public class Solution {
public int numDecodings(String s) {

if (s == null || s.length() == 0)
return 0;

Set<String> symbols = new HashSet<String>();
for (int i=1; i<=26; i++){
}

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
return numDec(s, 0,  map, symbols);
}

private int numDec(String str, int start,  Map<Integer, Integer> map, Set<String> symbols) {
Integer count = map.get(start);
if (count != null){
return count;
}

if (start == str.length()){
return 1;
}

int numWays = 0;
if ((start + 1 <= str. length()) &&
symbols.contains(str.substring(start, start + 1)) && symbols.contains(str.substring(start, start + 1)))
numWays += numDec(str, start + 1, map, symbols);

if ((start + 2 <= str. length()) &&
symbols.contains(str.substring(start, start + 2)) && symbols.contains(str.substring(start, start + 2)))
numWays += numDec(str, start + 2, map, symbols);

map.put(start, numWays);

return numWays;
}
}``````

• You write `symbols.contains(str.substring(start, start + 1))` and `symbols.contains(str.substring(start, start + 2))` twice. But I love your approach. I think I can call it Path-Memorizing DFS. BTW, I tried simple DFS and get TLE. I think after path-memorizing, the time complexity is O(n). Great!

• Really want to invite everyone to see your solution. You are the only one not using DP.

• actually, you dont need the symbols, just need a map, just calculate the 1 <= substr(1) <= 26, and 10 <= substr(2) <= 26

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