Backtracking with HashMap, easy to read.


  • 0
    M

    DFS with TLE, using hash map to store all prefix.

        public List<List<String>> wordSquares(String[] words) {
            List<List<String>> ans = new ArrayList<>();
            if (words == null || words.length == 0) {
                return ans;
            }
            Map<String, Set<String>> map = new HashMap<>();
            int len = words[0].length();
            for (int i = 1; i < len; i++) {
                for (String word : words) {
                    String key = word.substring(0, i);
                    if (!map.containsKey(key)) {
                        map.put(key, new HashSet<>());
                    }
                    map.get(key).add(word);
                }
            }
            for (int i = 0; i < words.length; i++) {
                List<String> temp = new ArrayList<>();
                temp.add(words[i]);
                backTracking(ans, temp, words, map);
            }
            return ans;
            
        }
        
        public void backTracking(List<List<String>> ans, List<String> temp, String[] words, Map<String, Set<String>> map) {
            if (temp.size() == words[0].length()) {
                ans.add(new ArrayList<>(temp));
                return;
            }
            Set<String> set = getPrefix(map, temp, temp.size());
            if (set != null) {
                for (String word : set) {
                    temp.add(word);
                    backTracking(ans, temp, words, map);
                    temp.remove(temp.size() - 1);
                }
            }
            
        }
        
        public Set<String> getPrefix(Map<String, Set<String>> map, List<String> temp, int len) {
            StringBuilder prefix = new StringBuilder();
            for (int i = 0; i < len; i++) {
                prefix.append(temp.get(i).charAt(len));
            }
            return map.get(prefix.toString());
        }    
    }
    

Log in to reply
 

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