425 Word Squares

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 alphabeta-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

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[0].length();
for (String word : words) {
square = new ArrayList();
square.add(word);
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) {
res.add(new ArrayList(square));
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) {
square.add(word);
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[26];
}
}
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.childNode[index].words.add(word);
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;
}
}
}

3. Time & Space Complexity