425. Word Squares

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

Note:

1. There are at least 1 and at most 1000 words.
2. All words will have the exact same length.
3. Word length is at least 1 and at most 5.
4. Each word contains only lowercase English alphabet a-z.

Example 1:

Input:
["area","lead","wall","lady","ball"]

Output:
[
  [ "wall",
    "area",
    "lead",
    "lady"
  ],
  [ "ball",
    "area",
    "lead",
    "lady"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Example 2:

Input:
["abat","baba","atan","atal"]

Output:
[
  [ "baba",
    "abat",
    "baba",
    "atan"
  ],
  [ "baba",
    "abat",
    "baba",
    "atal"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

参考
https://discuss.leetcode.com/topic/63516/explained-my-java-solution-using-trie-126ms-16-16


需要构造这个square，可以用backtracking。构造答案的时候check constraints

思路是典型思路，但是具体操作有所不同。

首先每一行的word可以重复，因此每次dfs的时候都是从所有words 中寻找合适的word

因此问题变成如何找合适的word

合适word：each word reads the same both horizontally and vertically.

当我们随便取n个word构成word square的时候，要看第i行是否与第i列相等。但是这样做cost 太大。

如果我们能够backtracking做就可以跳过不符合的word squares。因此我们需要转换“第i行是否与第i列相等”这个条件。

b a l l
a r e a
l e a d
l a d y

我们在看例子的时候可以发现只要按照图上构造就行。按照列的prefix来找行的word。

第二行的word就是满足prefix=='a'的那些word，第三行的word就是按照第二行取的结果满足prefix == 'le'（第三列的prefix）的那些wrod，第四行就是取以第四列prefix'lad'开头的words。如果没有答案就roll back 说明上面的构造不对。

因此在构造trie的时候，要在每个点存prefix是这个path的wordList

  class TrieNode{  
     TrieNode[] children;  
     List<String> wordList;  
     public TrieNode(){  
       children = new TrieNode[26];  
       wordList = new ArrayList<>();  
     }  
     public List<String> findWords(String prefix){  
       List<String> ans = new ArrayList<>();  
       List<TrieNode> candidates = new ArrayList<>();  
       candidates.add(root);  
       int n = prefix.length();  
       for(int i = 0; i < n; i++){  
         int t = prefix.charAt(i) - 'a';  
         int size = candidates.size();  
         for(int j = 0; j < size; j++){  
           TrieNode node = candidates.remove(0);  
           if(node.children[t]!=null){  
             candidates.add(node.children[t]);  
           }  
         }  
       }  
       for(TrieNode node: candidates){  
         ans.addAll(node.wordList);  
       }  
       return ans;  
     }  
   }  
   List<List<String>> ans = new ArrayList<>();  
   TrieNode root = null;  
   public List<List<String>> wordSquares(String[] words) {  
     root = buildTrie(words);  
     List<String> list = new ArrayList<>();
     //give every word a chance to be on top    
     for(String w: words){  
       list.add(w);  
       dfs(list,1,words[0].length());  
       list.remove(list.size()-1);  
     }  
     return ans;  
   }  
   public void dfs(List<String> list, int idx, int n){  
     if(idx == n){  
       ans.add(new ArrayList<>(list));  
       return;  
     }  
     //construct the prefix that needed to find next line word 
     //use trie to find words that start with those constraints, and dfs for each one of them  
     String prefix = "";  
     for(String s: list){  
       prefix+=s.charAt(idx);  
     }  
     List<String> words = root.findWords(prefix);  
     for(String word: words){  
       list.add(word);  
       dfs(list,idx+1,n);  
       list.remove(list.size()-1);  
     }  
   }  
   public TrieNode buildTrie(String[] words){  
     TrieNode root = new TrieNode();  
     for(int i = 0 ; i < words.length; i++){  
       String w = words[i];  
       TrieNode cur = root;  
       for(int j = 0; j < w.length(); j++){  
         int idx = w.charAt(j) - 'a';  
         if(cur.children[idx] == null){  
           cur.children[idx] = new TrieNode();  
         }  
         cur = cur.children[idx];  
         cur.wordList.add(words[i]);  
       }  
     }  
     return root;  
   }