-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathwordSquare.java
More file actions
82 lines (74 loc) · 2.23 KB
/
wordSquare.java
File metadata and controls
82 lines (74 loc) · 2.23 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.util.*;
public class wordSquare {
class TrieNode{
TrieNode[] children;
List<String> startWith;
TrieNode(){
children = new TrieNode[26];
startWith = new ArrayList<>();
}
}
class Trie{
TrieNode root;
Trie(){
root = new TrieNode();
}
void add (String word){
TrieNode cur = root;
for(char c : word.toCharArray()){
TrieNode next = cur.children[c-'a'];
if(next == null){
next = new TrieNode();
cur.children[c-'a'] = next;
}
next.startWith.add(word);
cur = next;
}
}
List<String> findByPrefix(String prefix){
List<String> res = new ArrayList<>();
TrieNode cur = root;
for(char c : prefix.toCharArray()){
TrieNode next = cur.children[c-'a'];
if(next == null) return res;
cur = next;
}
// add all. 别直接return了 node.startwith
res.addAll(cur.startWith);
return res;
}
}
public List<List<String>> wordSquares(String[] words){
List<List<String>> res = new ArrayList<>();
Trie trie = new Trie();
for(String word : words){
trie.add(word);
}
// dfs
int len = words[0].length();
for(String word : words){
List<String> path = new ArrayList<>();
path.add(word);
dfs(trie, len, path, res);
}
return res;
}
private void dfs(Trie trie, int len, List<String> path, List<List<String>> res ){
if(path.size() == len){
res.add(new ArrayList<>(path));
return;
}
StringBuilder prefix = new StringBuilder();
int size = path.size();
for(String word : path){
prefix.append(word.charAt(size));
}
List<String> words = trie.findByPrefix(prefix.toString());
// branches
for(String word : words){
path.add(word);
dfs(trie, len, path, res);
path.remove(path.size()-1);
}
}
}