Super Verbose Java Solution - DFS with Memoization


  • 0
    P

    Not the best approach but works.
    E.g. stickers - ["with", "example", "science"]
    target - "thehat"

    1. Convert the target word into a map of character counts (thehat - > {'t' : 2, 'h' : 2, 'e' : 1, 'a' : 1}
    2. Create a map of character to possible sticker options ({'t' : ["with"], 'h' : ["with"], 'e' : ["example", "science"], 'a' : ["example"] })
    3. Get the character which has minimum options available (i.e. minimum number of stickers to try from) (e.g. here 't', 'h' and 'a' can only be built from one kind of sticker, so we take one of these characters)
    4. Try each of the possible stickers in 'minOptions', try it, update the target character count, and repeat Step 3. To prevent recomputation, store results in Map.
    5. Return the minimum number of stickers needed.

    Running Time 250 ms.

    class Solution {
        
        Map<Character, List<String>> options;
        Map<String, Integer> table = new HashMap();
        
        public int minStickers(String[] stickers, String target) {
            Map<Character, Integer> charCounts = getCharCounts(target);
            if(!possible(stickers, charCounts)) {
                return -1;
            }       
            options = getOptions(stickers, charCounts);
            return minStickers(stickers, charCounts);
        }
        
        public int minStickers(String[] stickers, Map<Character, Integer> charCounts) {
            String key = getKey(charCounts);
            
            if(table.containsKey(key)) {
                return table.get(key);
            }
            
            List<String> minOptions = getMinOptions(charCounts);
            int minStickers = Integer.MAX_VALUE;
            
            for(int i= 1; i < minOptions.size(); i++) {
                String word = minOptions.get(i);
                
                Map<Character, Integer> updateMap = update(charCounts, word );
                
                if(updateMap.size() == 0) {
                    return 1;
                }
                
                int stickerl = minStickers(stickers, updateMap);
                minStickers = Math.min(minStickers, stickerl + 1);
            }
            
            minStickers = minStickers == Integer.MAX_VALUE ? 0 : minStickers;
            table.put(key, minStickers);
            return minStickers;
        }
        
        public Map<Character, List<String>> getOptions(String[] stickers, Map<Character, Integer> charCounts) {
            Map<Character, List<String>> options = new HashMap();
            
            for(char c : charCounts.keySet()) {
                List<String> words = new ArrayList();
                
                for(String sticker : stickers) {
                    if(sticker.indexOf(c) >= 0) {
                        words.add(sticker);
                    }
                }
                
                options.put(c, words);
            }
            
            return options;
        }
        
        public List<String> getOptions(Map<Character, Integer> charCounts) {
            char minChar = '0';
            List<String> minOptions = null;
            int minLength = Integer.MAX_VALUE;
            
            for(char c : charCounts.keySet()) {
                List<String> optionsList = options.get(c);
                
                if(optionsList.size() < minLength) {
                    minLength = optionsList.size();
                    minChar = c;
                    minOptions = new ArrayList();
                    minOptions.add(c+"");
                    minOptions.addAll(optionsList);
                }
            }
            
            return minOptions;
        }
        
        public Map<Character, Integer> getCharCounts(String target) {
            Map<Character, Integer> map = new HashMap();
            
            for(int i = 0; i < target.length(); i++) {
                char c = target.charAt(i);
                if(map.containsKey(c)) {
                    map.put(c, map.get(c) + 1);
                }
                else {
                    map.put(c, 1);
                }
            }
            
            return map;
        }
        
        public Map<Character, Integer> update(Map<Character, Integer> charCounts, String word) {
            Map<Character, Integer> updateMap = new HashMap(charCounts);
            
            for(int i = 0 ; i < word.length(); i++) {
                char c = word.charAt(i);
                
                if(updateMap.containsKey(c)) {
                    updateMap.put(c, updateMap.get(c) - 1);
                    
                    if(updateMap.get(c) == 0) {
                        updateMap.remove(c);
                    }
                }
            }
            
            return updateMap;
        }
        
        public boolean possible(String[] stickers, Map<Character, Integer> charCounts) {
            for(char c : charCounts.keySet()) {
                boolean possible = false;
                for(String sticker : stickers) {
                    if(sticker.indexOf(c) >= 0) {
                        possible = true;
                    }
                }
                if(!possible) {
                    return false;
                }
            }
            return true;
        }
        
        public String getKey(Map<Character, Integer> charCounts) {
            List<Character> list = new ArrayList();
            
            for(char c : charCounts.keySet()) {
                for(int i = 0; i < charCounts.get(c); i++) {
                    list.add(c);
                }
            }
            
            Collections.sort(list);
            
            StringBuilder s = new StringBuilder();
            for(Character c : list) {
                s.append(c);
            }
            
            return s.toString();
        }
    }
    

Log in to reply
 

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