Sharing my java memoized solution


  • 13
    M
    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++){
            	symbols.add(String.valueOf(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;
        }
    }

  • 3
    S

    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!


  • 1
    S

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


  • 1
    L

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


Log in to reply
 

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