# 0425. Word Squares
###### tags: `Leetcode` `Hard` `Trie` `Simulation`
Link: https://leetcode.com/problems/word-squares/description/
## 思路
为了帮助理解题意 这里先举个例子 有一种答案是 ["ball","area","lead","lady"]
构建完之后就是
每个单词占一行 第i行和第i列的单词是一模一样的
直接的方法是我们可以用backtracking解
先固定第一个单词 再找到符合要求的第二个单词(以第一个单词的第二个字母开头)
接下来找到符合要求的第三个单词(以第一个单词和第二个单词的第三个字母开头)
以此类推...
但是直接这样做会TLE 因为我们要检查每一个单词看是不是startwith前```i```个单词的```i+1```位 所以我们用Trie优化
## Code

class Solution {
    List<List<String>> ans;
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
        List<Integer> preWords = new ArrayList<>();
    }
    TrieNode root;
    public List<List<String>> wordSquares(String[] words) {
        ans = new ArrayList<>();
        root = new TrieNode();
        for(int i=0; i<words.length; i++){
            addWord(words[i], i);
        }
        for(int i=0; i<words.length; i++){
            List<String> tmp = new ArrayList<>();
            tmp.add(words[i]);
            backtracking(tmp, words);
        }
        return ans;
    }
    public void addWord(String word, int idx){
        TrieNode curr = root;
        for(int i=0; i<word.length(); i++){
            if(curr.children[word.charAt(i)-'a']==null) curr.children[word.charAt(i)-'a'] = new TrieNode();
            curr = curr.children[word.charAt(i)-'a'];
            curr.preWords.add(idx);
        }
    }
    public void backtracking (List<String> seq, String[] words){
        if(seq.size()==words[0].length()){
            ans.add(new ArrayList<>(seq));
            return;
        }
        int size = seq.size();
        TrieNode curr = root;
        for(int i=0; i<size; i++){
            char c = seq.get(i).charAt(size);
            if(curr.children[c-'a']==null) return;
            curr = curr.children[c-'a'];
        }
        for(int idx:curr.preWords){
            String word = words[idx];
            seq.add(word);
            backtracking(seq, words);
            seq.remove(seq.size()-1);
        }
    }
}