Given a set of words(without duplicates), find allword squaresyou can build from them.

A sequence of words forms a valid word square if thekthrow and column read the exact same string, where 0 ≤k< max(numRows, numColumns).

For example, the word sequence["ball","area","lead","lady"]forms a word square because each word reads the same both horizontally and vertically.

b a l l
a r e a
l e a d
l a d y

Note:

1. There are at least 1 and at most 1000 words.
2. All words will have the exact same length.
3. Word length is at least 1 and at most 5.
4. Each word contains only lowercase English alphabeta-z.

这道题我只想出了暴力解法，一个一个地去试，但是即使提示之后也没有想明白怎么用trie，看了这个答案之后才明白https://leetcode.com/problems/word-squares/discuss/91354/Java-DFS%2BTrie-54-ms-98-so-far

大概思路是建立一个trie，再建立一个trie node数组，里面开始只存root

然后选择row和col相同的字符的trie中的路径，行数row不变，col + 1，这时col + 1就指向了下一个数组中的node，也就是root，即为下一个词的首字母

class Solution {
    class Node {
        public Node[] children;
        public String word;

        public Node() {
            this.children = new Node[26];
            this.word = null;
        }
    }

    public void add(Node root, String word) {
        Node temp = root;
        for(int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);

            if(temp.children[c - 'a'] == null)
                temp.children[c - 'a'] = new Node();
            temp = temp.children[c - 'a'];
        }

        temp.word = word;
    }

    public List<List<String>> wordSquares(String[] words) {
        List<List<String>> res = new ArrayList<>();
        if(words == null || words.length == 0)
            return res;

        Node root = new Node();
        for(String word: words) {
            add(root, word);
        }

        int len = words[0].length();
        Node[] rows = new Node[len];
        for(int i = 0; i < len; i++)
            rows[i] = root;

        helper(res, rows, 0, 0, len);

        return res;
    }

    public void helper(List<List<String>> res, Node[] rows, int row, int col, int len) {
        if(row == col && row == len) {
            List<String> solution = new ArrayList<>();
            for(Node r: rows)
                solution.add(r.word);
            res.add(solution);
            return;
        }

        if(col < len) {
            Node prevRow = rows[row];
            Node prevCol = rows[col];

            for(int i = 0; i < 26; i++) {
                if(prevRow.children[i] != null && prevCol.children[i] != null) {
                    rows[row] = prevRow.children[i];
                    rows[col] = prevCol.children[i];
                    helper(res, rows, row, col + 1, len);
                    rows[row] = prevRow;
                    rows[col] = prevCol;
                }
            }
        } else {
            helper(res, rows, row + 1, row + 1, len);
        }
    }
}