Lintcode634 Word Squares

来源：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

可以发现规律就是找到第一个string后，第二个string是以第一个string第二个字母开头，第三个string是以前两个string的第三个字母开头，第四个string是以前三个string第四个字母开头

所以每次新加进list<string>的单词都是以list现有的string.charAt(list.size()) 为开头

本题应用到了字典树，树内有26个字母和此时以此字母开始的单词。

整体结构就是开始遍历words, 把每个word加入到一个list里，然后以此展开深搜寻找，每次都是以现有的prefix来在字典寻找下一个可能的单词。一旦list<string> 的单词数目达到单词长度的级别，那么一个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];
}