# 425 Word Squares

## 1. Question

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 thekthrow 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. 1.
There are at least 1 and at most 1000 words.
2. 2.
All words will have the exact same length.
3. 3.
Word length is at least 1 and at most 5.
4. 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

## 2. Implementation

(1) Backtracking
class Solution {
public List<List<String>> wordSquares(String[] words) {
List<List<String>> res = new ArrayList();
if (words == null || words.length == 0) {
return res;
}
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
List<String> square = null;
int len = words.length();
for (String word : words) {
square = new ArrayList();
searchSquare(len, trie, square, res);
}
return res;
}
public void searchSquare(int len, Trie trie, List<String> square, List<List<String>> res) {
if (square.size() == len) {
return;
}
int index = square.size();
StringBuilder prefix = new StringBuilder();
for (String word : square) {
prefix.append(word.charAt(index));
}
List<String> words = trie.searchPrefix(prefix.toString());
if (words == null) {
return;
}
for (String word : words) {
searchSquare(len, trie, square, res);
square.remove(square.size() - 1);
}
}
class TrieNode {
char val;
boolean isWord;
List<String> words;
TrieNode[] childNode;
public TrieNode(char val) {
this.val = val;
words = new ArrayList();
childNode = new TrieNode;
}
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode(' ');
}
public void insert(String word) {
if (word == null || word.length() == 0) {
return;
}
TrieNode curNode = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (curNode.childNode[index] == null) {
curNode.childNode[index] = new TrieNode(c);
}
curNode = curNode.childNode[index];
}
curNode.isWord = true;
}
public List<String> searchPrefix(String word) {
if (word == null || word.length() == 0) {
return null;
}
TrieNode curNode = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (curNode.childNode[index] == null) {
return null;
}
curNode = curNode.childNode[index];
}
return curNode.words;
}
}
}