來源：LintCode

Given a set of words without duplicates, find all word squares you 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

可以發(fā)現(xiàn)規(guī)律就是找到第一個string后浪听，第二個string是以第一個string第二個字母開頭蚯斯，第三個string是以前兩個string的第三個字母開頭火的，第四個string是以前三個string第四個字母開頭

所以每次新加進(jìn)list<string>的單詞都是以list現(xiàn)有的string.charAt(list.size()) 為開頭

本題應(yīng)用到了字典樹嘹叫，樹內(nèi)有26個字母和此時(shí)以此字母開始的單詞。

整體結(jié)構(gòu)就是開始遍歷words, 把每個word加入到一個list里，然后以此展開深搜尋找呻澜，每次都是以現(xiàn)有的prefix來在字典尋找下一個可能的單詞纠屋。一旦list<string> 的單詞數(shù)目達(dá)到單詞長度的級別涂臣，那么一個square形成。 代碼如下

class Solution {
   public List<List<String>> wordSquares(String[] words) {
        // write your code here
        Trie t = new Trie();
        
        for(String str: words){
            Build(t, str);
        }
        
        List<List<String>> ans = new ArrayList<>();
        int len = words[0].length();
        

        for(int i = 0; i < words.length; i++){
            List<String> ls = new ArrayList<>();
            ls.add(words[i]);
           
            search(len, t, ans, ls);
        }

        return ans;

        
    }
    private void search(int len, Trie tr, List<List<String>> ans,
            List<String> ansBuilder) {
        if (ansBuilder.size() == len) {
            ans.add(ansBuilder);
            return;
        }

        int idx = ansBuilder.size();
        StringBuilder prefixBuilder = new StringBuilder();
        for (String s : ansBuilder)
            prefixBuilder.append(s.charAt(idx));
        List<String> startWith = findPrefix(tr, prefixBuilder.toString());
        for (String sw : startWith) {
            List<String> next = new ArrayList<>(ansBuilder);
            next.add(sw);
            search(len, tr, ans, next);
        }
    }
    
    private void Build(Trie t, String word){
        Trie p = t;
        for(int i = 0; i < word.length(); i++){
            int index = word.charAt(i) - 'a';
            if(p.tries[index] == null){
                p.tries[index] = new Trie();
            }
            p.tries[index].startWith.add(word);
            
           
            p = p.tries[index];
        }
    }
    public List<String> findPrefix(Trie t, String prefix){
        Trie root = t;
        List<String> ans = new ArrayList<>();
        for(int i = 0; i < prefix.length(); i++){
            int index = prefix.charAt(i) - 'a';
            if(root.tries[index] == null){
                return ans;
            }
            root = root.tries[index];
        }
        
         ans.addAll(root.startWith);
        return ans;
    }
}
class Trie{
    List<String> startWith = new ArrayList<>();
    Trie[] tries = new Trie[26];
}