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.
1
b a l l
2
a r e a
3
l e a d
4
l a d y
Copied!
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:
1
Input:
2
["area","lead","wall","lady","ball"]
3
4
5
Output:
6
7
[
8
[ "wall",
9
"area",
10
"lead",
11
"lady"
12
],
13
[ "ball",
14
"area",
15
"lead",
16
"lady"
17
]
18
]
19
20
Explanation:
21
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).
Copied!
Example 2:
1
Input:
2
3
["abat","baba","atan","atal"]
4
5
6
Output:
7
[
8
[ "baba",
9
"abat",
10
"baba",
11
"atan"
12
],
13
[ "baba",
14
"abat",
15
"baba",
16
"atal"
17
]
18
]
19
20
21
Explanation:
22
The output consists of two word squares. The order of output does not matter (just the order of words in each
Copied!

2. Implementation

(1) Backtracking
1
class Solution {
2
public List<List<String>> wordSquares(String[] words) {
3
List<List<String>> res = new ArrayList();
4
5
if (words == null || words.length == 0) {
6
return res;
7
}
8
9
Trie trie = new Trie();
10
11
for (String word : words) {
12
trie.insert(word);
13
}
14
15
List<String> square = null;
16
int len = words[0].length();
17
18
for (String word : words) {
19
square = new ArrayList();
20
square.add(word);
21
searchSquare(len, trie, square, res);
22
}
23
return res;
24
}
25
26
public void searchSquare(int len, Trie trie, List<String> square, List<List<String>> res) {
27
if (square.size() == len) {
28
res.add(new ArrayList(square));
29
return;
30
}
31
32
int index = square.size();
33
34
StringBuilder prefix = new StringBuilder();
35
36
for (String word : square) {
37
prefix.append(word.charAt(index));
38
}
39
40
List<String> words = trie.searchPrefix(prefix.toString());
41
42
if (words == null) {
43
return;
44
}
45
46
for (String word : words) {
47
square.add(word);
48
searchSquare(len, trie, square, res);
49
square.remove(square.size() - 1);
50
}
51
}
52
53
class TrieNode {
54
char val;
55
boolean isWord;
56
List<String> words;
57
TrieNode[] childNode;
58
59
public TrieNode(char val) {
60
this.val = val;
61
words = new ArrayList();
62
childNode = new TrieNode[26];
63
}
64
}
65
66
class Trie {
67
TrieNode root;
68
69
public Trie() {
70
root = new TrieNode(' ');
71
}
72
73
public void insert(String word) {
74
if (word == null || word.length() == 0) {
75
return;
76
}
77
78
TrieNode curNode = root;
79
80
for (char c : word.toCharArray()) {
81
int index = c - 'a';
82
83
if (curNode.childNode[index] == null) {
84
curNode.childNode[index] = new TrieNode(c);
85
}
86
curNode.childNode[index].words.add(word);
87
curNode = curNode.childNode[index];
88
}
89
curNode.isWord = true;
90
}
91
92
public List<String> searchPrefix(String word) {
93
if (word == null || word.length() == 0) {
94
return null;
95
}
96
97
TrieNode curNode = root;
98
99
for (char c : word.toCharArray()) {
100
int index = c - 'a';
101
102
if (curNode.childNode[index] == null) {
103
return null;
104
}
105
curNode = curNode.childNode[index];
106
}
107
return curNode.words;
108
}
109
}
110
}
Copied!

3. Time & Space Complexity