DFS + HashMap, 56 lines, 148ms


  • 0
    S

    The idea is the same as lzb700m, (https://discuss.leetcode.com/topic/63516/explained-my-java-solution-using-trie-126ms-16-16). Use a hash map instead of tire for simplicity

            public List<List<String>> wordSquares(String[] words) {
                HashMap<String, Set<String>> wordPrefix = new HashMap<>();
                List<List<String>> result = new ArrayList<>();
                if (words == null || words.length == 0) return result;
                if (words.length == 1 && words[0].length() == 1) {
                    List<String> rr = new ArrayList<>();
                    rr.add(words[0]);
                    result.add(rr);
                    return result;
                }
                for (int i = 0; i < words.length; i++) {
                    String w = words[i];
                    for (int j = 1; j <= w.length(); j++) {
                        String prefix = w.substring(0, j);
                        if (!wordPrefix.containsKey(prefix)){
                            wordPrefix.put(prefix, new HashSet<>());
                        }
                        wordPrefix.get(prefix).add(w);
                    }
                }
                for (String w : words) {
                    char[] wcs = w.toCharArray();
                    char[][] board = new char[wcs.length][wcs.length];
                    board[0] = wcs;
                    findPrefix(wordPrefix, board, 1, result);
                }
                return result;
            }
    
            private char[] getCol(char[][] board, int index) {
                char[] chars = new char[index];
                for (int i  = 0; i < chars.length; i++) {
                    chars[i] = board[i][index];
                }
                return chars;
            }
    
            private List<String> toStringList(char[][] board) {
                List<String> r = new ArrayList<>();
                for (char[] chars : board) {
                    r.add(new String(chars));
                }
                return r;
            }
    
            private void findPrefix(HashMap<String, Set<String>> wordPrefix, char[][] board, int index, List<List<String>> result) {
                char[] prefixChars = getCol(board, index);
                String prefixStr = new String(prefixChars);
                Set<String> words = wordPrefix.get(prefixStr);
                if (words != null) {
                    for (String w : words) {
                        char[][] subBoard = board.clone();
                        subBoard[index] = w.toCharArray();
                        if (index + 1 == board.length) {
                            result.add(toStringList(subBoard));
                        } else {
                            findPrefix(wordPrefix, subBoard, index + 1, result);
                        }
                    }
                }
            }
    

  • 0

    Using Trie is simpler and easier, and needs less space.


Log in to reply
 

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