Short Java solution without trie


  • 0
    I
    public class Solution {
        private void wordSquares(Map<String, List<String>> prefixes, List<List<String>> allSquares, List<String> currentSquare, int size) {
            if (currentSquare.size() == size) {
                allSquares.add(new ArrayList<>(currentSquare));
            } else {
                StringBuilder prefix = new StringBuilder();
                for (int i = 0; i < currentSquare.size(); i++)
                    prefix.append(currentSquare.get(i).charAt(currentSquare.size()));
    
                List<String> candidates = prefixes.get(prefix.toString());
                if (candidates != null) {
                    for (String candidate : candidates) {
                        currentSquare.add(candidate);
                        wordSquares(prefixes, allSquares, currentSquare, size);
                        currentSquare.remove(currentSquare.size() - 1);
                    }
                }
            }
        }
    
    
        public List<List<String>> wordSquares(String[] words) {
            if (words.length == 0) return new ArrayList<>();
    
            Map<String, List<String>> prefixes = new HashMap<>();
            for (String word : words) {
                for (int j = 0; j < words[0].length(); j++) {
                    String prefix = word.substring(0, j);
                    if (!prefixes.containsKey(prefix)) prefixes.put(prefix, new ArrayList<>());
                    prefixes.get(prefix).add(word);
                }
            }
    
            List<List<String>> allSquares = new ArrayList<>();
            wordSquares(prefixes, allSquares, new ArrayList<>(), words[0].length());
    
            return allSquares;
        }   
    }
    

Log in to reply
 

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