Given a set of wordswithout duplicates, find allword squaresyou can build from them.

A sequence of words forms a valid word square if the kth row 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

Notice

• There are at least 1 and at most 1000 words.
• All words will have the exact same length.
• Word length is at least 1 and at most 5.

• Each word contains only lowercase English alphabet a-z .

• 暴力解法

递归寻求不同的permuation, 然后通过一个函数来判断是否是square, 这个方法很快就超时了

public class Solution {
    /*
     * @param words: a set of words without duplicates
     * @return: all word squares
     */
    public List<List<String>> wordSquares(String[] words) {
        // write your code here
        List<List<String>> ans = new ArrayList<>();
        if (words == null || words.length == 0) {
            return ans;
        }
        List<String> cur = new ArrayList<>();
        dfs(words, cur, ans);
        return ans;
    }

    public void dfs(String[] words, List<String> cur, List<List<String>> ans) {
        if (cur.size() != 0 && cur.size() == cur.get(0).length()) {
            if (isSquare(cur)) {
                ans.add(new ArrayList<String>(cur));
            }
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (cur.size() != 0 && words[i].length() != cur.get(0).length()) {
                continue;
            }
            cur.add(words[i]);
            dfs(words, cur, ans);
            cur.remove(cur.size() - 1);
        }
    }

    public boolean isSquare(List<String> cur) {
        char[][] square = new char[cur.size()][cur.size()];
        for (int i = 0; i < cur.size();i++) {
            for (int j = 0; j < cur.size(); j++) {
                square[i][j] = cur.get(i).charAt(j);
            }
        }
        int i = 1;
        while (i < cur.size()) {
            int k = 0;
            int q = 0;
            while (k < i && q < i) {
                if (square[i][k] != square[q][i]) {
                    return false;
                }
                q++;
                k++;
            }
            i++;
        }
        return true;
    }
}

1. 用前缀查询，通过遍历字典树组合出每个可能的word sqaure

关键思路：

1. 用到了字典树通过一个prefix查找所有可能的性质
2. 在square集合中有几个词，由所有词在词个数下一位所组成的词为下一个词的前缀

abcd

bdea

下一个词的前缀就是由第三个字符所组成的词 ce + ...

class TrieNode {
    HashMap<Character, TrieNode> children = null;
    boolean hasWord;
    String word;
    public TrieNode() {
        children = new HashMap<Character, TrieNode>();
        hasWord = false;
        word = "";
    }
}

class Trie {
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        char[] wordA = word.toCharArray();
        TrieNode cur = this.root;
        for (int i = 0; i < wordA.length; i++) {
            if (!cur.children.containsKey(wordA[i])) {
                cur.children.put(wordA[i], new TrieNode());
            }
            cur = cur.children.get(wordA[i]);
        }
        cur.hasWord = true;
        cur.word = word;
    }

    public boolean findPrefix(String prefix) {
        char[] wordA = prefix.toCharArray();
        TrieNode cur = this.root;
        for (int i = 0; i < wordA.length; i++) {
            if (!cur.children.containsKey(wordA[i])) {
                return false;
            }
            cur = cur.children.get(wordA[i]);
        }
        return true;
    }

    public boolean findWord(String word) {
        char[] wordA = word.toCharArray();
        TrieNode cur = this.root;
        for (int i = 0; i < wordA.length; i++) {
            if (!cur.children.containsKey(wordA[i])) {
                return false;
            }
            cur = cur.children.get(wordA[i]);
        }
        return cur.hasWord;
    }

    private void dfs(TrieNode cur, List<String> ans) {
        if (cur.hasWord) {
            ans.add(cur.word);
        }

        for (Character c : cur.children.keySet()) {
            dfs(cur.children.get(c), ans);
        }
    }
    public List<String> findForPrefix (String prefix) {
        char[] wordA = prefix.toCharArray();
        TrieNode cur = this.root;
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < prefix.length(); i++) {
            if (!cur.children.containsKey(wordA[i])) {
                return ans;
            }
            cur = cur.children.get(wordA[i]);
        }
        dfs(cur, ans);
        return ans;

    }
}

public class Solution {
    /*
     * @param words: a set of words without duplicates
     * @return: all word squares
     */
    public List<List<String>> wordSquares(String[] words) {
        // write your code here
        List<List<String>> ans = new ArrayList<>();
        if (words == null || words.length == 0) {
            return ans;
        }
        Trie trie = new Trie();
        for (int i = 0; i < words.length; i++) {
            trie.insert(words[i]);
        }

        //List<String> cur = trie.findForPrefix("at");
        // for (String c : cur) {
        //     System.out.println(c);
        // }
        List<String> square = new ArrayList<>();
        for (String word : words) {
            square.add(word);
            dfs(word.length(), square, ans, trie);
            square.remove(square.size() - 1);
        }   
        return ans;
    }

    public void dfs(int len, List<String> square, List<List<String>> ans, Trie trie) {
        if (square.size() == len) {
            ans.add(new ArrayList<String>(square));
            return;
        }

        int index = square.size();
        StringBuilder prefix = new StringBuilder();
        for (String curWord : square) {
            prefix.append(curWord.charAt(index));
        }
        List<String> candidates = trie.findForPrefix(prefix.toString());

        for (String candidate : candidates) {
            square.add(candidate);
            dfs(len, square, ans, trie);
            square.remove(square.size() - 1);
        }

    }
}