Java easy to understand Backtracking + HashMap


  • 1
    J
    class Solution {
        
        public List<List<String>> wordSquares(String[] words) {
            
            Map<String, Set<String>> map = new HashMap<>();
            for(String word: words) {
                for(int i = 1; i < word.length(); i ++) {
                    String prefix = word.substring(0, i);
                    if(!map.containsKey(prefix)) map.put(prefix, new HashSet<>());
                    map.get(prefix).add(word);
                }
            }
            
            List<List<String>> ans = new ArrayList<>();
            List<String> temp = new ArrayList<String>();
            for(int i = 0; i < words.length; i ++) {
                temp.add(words[i]);
                find(ans, 1, temp, map);
                temp.remove(words[i]);
            }
            return ans;
        }
        
        public void find(List<List<String>> ans, int pos, List<String> temp, Map<String, Set<String>> map) {
            
            if(temp.size() == temp.get(0).length()) {
                ans.add(new ArrayList<>(temp));
                return;
            }
            
            String prefix = "";
            for(int i = 0; i < pos; i ++) {
                prefix += temp.get(i).charAt(pos);
            }
            if(!map.containsKey(prefix)) return;
            
            for(String word: map.get(prefix)) {
                temp.add(word);
                find(ans, pos + 1, temp, map);
                temp.remove(temp.size() - 1);        
            }
        }
    }
    

Log in to reply
 

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