# 425 Word Squares

word square的意思是一個由若干字串組成的長寬相同的方形， 直的讀和橫著讀都是一樣的字。 例如

[ "wall",
  "area",
  "lead",
  "lady"
]

input: list of words（長度相同） output: list of list of words 所有可以組成word square的組合。

Concept: 將input word建成Trie, 每個TrieNode要有TrieNode next[]，還要有一個hash set記錄有哪些字可以到這個TrieNode。

把每個word都當成list中的第一個看看，第二個就要找開頭和第一個的第二個字母相同的word，若找不到，就放棄讓這個word當第一個，若找到了，再找開頭和word的第三個字母相同的word...

Implementation:

1. Main: 先把tree建好，建好後一個for迴圈跑過每個word(讓每個word當list中的第一個)，接下來要找過每一個字是否可以當第二個、第三個...一直重複，可以用recursive來做，所以寫另一個helper function來找。
2. helper(): 進入help之後，先確認當前list的長度是否已經和字母數量一樣，如果是代表此list已經完成word square，存進res。若list還沒滿，則要繼續找可以符合已經存在list中的字下一個字。 如何找符合的字呢？假如現在要找list中的第n個字，先在trie中找到第1個字的第n-1個char，再繼續看這個trienode有沒有child符合第2個字的第n-1個char...實作這部分的pseudocode:

   TrieNode p=root
   for each entry in list
    //我們找的字必須和已經在list中的字的第list.size()個字直的讀下來相同。
    p = p.next[list.get(i).charAt(list.size())-'a'];
   if p is null, or p.set is null,
    表示沒有字和已經在list中的字的第list.size()個字直的讀下來相同
   for each entry in p.set
    put entry into list
    helper()
    remove entry from list
   

Code:

public class Solution {
    public List<List<String>> wordSquares(String[] words) {
        List<List<String>> res = new LinkedList<>();
        if(words==null || words.length==0) return res; 
        int len = words[0].length();
        Node root = new Node();
        for(String s: words){//build tree
            Node p = root; 
            p.set.add(s);
            for(char c: s.toCharArray()){
                if(p.next[c-'a']==null) p.next[c-'a'] = new Node();
                p = p.next[c-'a']; 
                p.set.add(s);
            }
        }
        List<String> cur = new LinkedList<>(); 
        helper(cur, root, res, len);
        return res; 
    }

    private void helper(List<String> cur, Node root, List<List<String>> res, int len){
        //System.out.println(cur);
        if(cur.size()==len){
            res.add(new ArrayList<String>(cur));
        }else{
            Node p = root; 
            for(int i = 0; i<cur.size(); i++){//match previous placed strings
                if(p==null || p.set.size()==0) return;
                p = p.next[cur.get(i).charAt(cur.size())-'a'];
            }
            if(p==null || p.set.size()==0) return;
            for(String s: p.set){
                cur.add(s);
                helper(cur, root, res, len);
                cur.remove(cur.size()-1);
            }
        }
    }
    class Node{
        Node[] next = new Node[26];
        Set<String> set = new HashSet<>();
    }
}