## Monday, October 17, 2016

### LeetCode 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:

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

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).```
X. DFS
https://discuss.leetcode.com/topic/63516/explained-my-java-solution-using-trie-126ms-16-16
My first approach is brute-force, try every possible word sequences, and use the solution of Problem 422 (https://leetcode.com/problems/valid-word-square/) to check each sequence. This solution is straightforward, but too slow (TLE).
A better approach is to check the validity of the word square while we build it.
Example: `["area","lead","wall","lady","ball"]`
We know that the sequence contains 4 words because the length of each word is 4.
Every word can be the first word of the sequence, let's take `"wall"` for example.
Which word could be the second word? Must be a word start with `"a"` (therefore `"area"`), because it has to match the second letter of word `"wall"`.
Which word could be the third word? Must be a word start with `"le"` (therefore `"lead"`), because it has to match the third letter of word `"wall"` and the third letter of word `"area"`.
What about the last word? Must be a word start with `"lad"` (therefore `"lady"`). For the same reason above.
The picture below shows how the prefix are matched while building the sequence.
In order for this to work, we need to fast retrieve all the words with a given prefix. There could be 2 ways doing this:
1. Using a hashtable, key is prefix, value is a list of words with that prefix.
2. Trie, we store a list of words with the prefix on each trie node.
One pic to help understand the Trie structure.
The only difference between the trie here and the normal trie is that we hold one more list of all the words which have the prefix(from the root char to the current node char).

``````    class TrieNode {
List<String> startWith;
TrieNode[] children;

TrieNode() {
startWith = new ArrayList<>();
children = new TrieNode[26];
}
}

class Trie {
TrieNode root;

Trie(String[] words) {
root = new TrieNode();
for (String w : words) {
TrieNode cur = root;
for (char ch : w.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null)
cur.children[idx] = new TrieNode();
cur = cur.children[idx];
}
}
}

List<String> findByPrefix(String prefix) {
List<String> ans = new ArrayList<>();
TrieNode cur = root;
for (char ch : prefix.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null)
return ans;

cur = cur.children[idx];
}
return ans;
}
}

public List<List<String>> wordSquares(String[] words) {
List<List<String>> ans = new ArrayList<>();
if (words == null || words.length == 0)
return ans;
int len = words[0].length();
Trie trie = new Trie(words);
List<String> ansBuilder = new ArrayList<>();
for (String w : words) {
search(len, trie, ans, ansBuilder);
ansBuilder.remove(ansBuilder.size() - 1);
}

return ans;
}

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

int idx = ansBuilder.size();
StringBuilder prefixBuilder = new StringBuilder();
for (String s : ansBuilder)
prefixBuilder.append(s.charAt(idx));
List<String> startWith = tr.findByPrefix(prefixBuilder.toString());
for (String sw : startWith) {
search(len, tr, ans, ansBuilder);
ansBuilder.remove(ansBuilder.size() - 1);
}
}``````
https://discuss.leetcode.com/topic/63532/121ms-java-solution-using-trie-and-backtracking
``````    TrieNode root = new TrieNode();
public List<List<String>> wordSquares(String[] words) {
List<List<String>> ans = new ArrayList<>();
if(words.length == 0) return ans;
buildTrie(words);
int length = words[0].length();
findSquare(ans, length, new ArrayList<>());
return ans;
}

private void findSquare(List<List<String>> ans, int length, List<String> temp) {
if(temp.size() == length) {
return;
}
int index = temp.size();
StringBuilder sb = new StringBuilder();
for(String s : temp) {
sb.append(s.charAt(index));
}
String s = sb.toString();
TrieNode node = root;
for(int i = 0; i < s.length(); i++) {
if(node.next[s.charAt(i) - 'a'] != null) {
node = node.next[s.charAt(i) - 'a'];
} else {
node = null;
break;
}
}
if(node != null) {
for(String next : node.words) {
findSquare(ans, length, temp);
temp.remove(temp.size() - 1);
}
}
}

private void buildTrie(String[] words) {
for(String word : words) {
TrieNode node = root;
char[] array = word.toCharArray();
for(char c : array) {
if(node.next[c - 'a'] == null) {
node.next[c - 'a'] = new TrieNode();
}
node = node.next[c - 'a'];
}
}
}

class TrieNode {
TrieNode[] next = new TrieNode[26];
List<String> words = new ArrayList<>();
}``````

https://discuss.leetcode.com/topic/63417/181-ms-java-solution-intuitive-backtracking

```首先构建一个单词前缀prefix->单词word的字典mdict

X. Using Trie
https://discuss.leetcode.com/topic/63516/my-java-solution-using-trie
`````` class TrieNode {
List<String> startWith;
TrieNode[] children;

TrieNode() {
startWith = new ArrayList<>();
children = new TrieNode[26];
}
}

class Trie {
TrieNode root;

Trie(String[] words) {
root = new TrieNode();
for (String w : words) {
TrieNode cur = root;
for (char ch : w.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null)
cur.children[idx] = new TrieNode();
cur = cur.children[idx];
}
}
}

List<String> findPrefix(String prefix) {
List<String> ans = new ArrayList<>();
TrieNode cur = root;
for (char ch : prefix.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null)
return ans;

cur = cur.children[idx];
}
return ans;
}
}

public List<List<String>> wordSquares(String[] words) {
List<List<String>> ans = new ArrayList<>();
if (words == null || words.length == 0)
return ans;
int n = words.length;
int len = words[0].length();
Trie trie = new Trie(words);
List<String> ansBuilder = new ArrayList<>();
for (String w : words) {
search(words, n, len, trie, ans, ansBuilder);
ansBuilder.remove(ansBuilder.size() - 1);
}

return ans;
}

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

int idx = ansBuilder.size();
StringBuilder prefix = new StringBuilder();
for (String s : ansBuilder)
prefix.append(s.charAt(idx));
List<String> startWith = tr.findPrefix(prefix.toString());
for (String sw : startWith) {
search(ws, n, len, tr, ans, ansBuilder);
ansBuilder.remove(ansBuilder.size() - 1);
}
}``````
https://discuss.leetcode.com/topic/64770/java-dfs-trie-54-ms-98-so-far/2