blob: 421d670e09d85fc6625f66ab41f8a166d27a3bf8 (
plain)
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
package org.guru.boggle;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Set;
import com.google.common.base.Objects;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Sets;
public class DictionaryTrie {
private static class Node {
private boolean wordEndsHere;
private final Node[] children = new Node[26];
public Node(boolean wordEndsHere) {
this.wordEndsHere = wordEndsHere;
}
private int letterToIndex(char letter) {
Preconditions.checkArgument(letter >= 'A' && letter <= 'Z', "Expect uppercase letter");
return letter - 'A';
}
// nullable
public Node childForLetter(char letter) {
return children[letterToIndex(letter)];
}
public void addChildAtLetter(Node child, char letter) {
Preconditions.checkState(!hasChildAtLetter(letter), "I already have a child");
children[letterToIndex(letter)] = child;
}
public boolean hasChildAtLetter(char letter) {
return children[letterToIndex(letter)] != null;
}
public Set<Character> childrenList() {
Set<Character> result = Sets.newHashSetWithExpectedSize(8);
for (int i = 0; i < 26; ++i) {
if (children[i] != null) {
result.add((char) (i + 'A'));
}
}
return result;
}
public boolean doesWordEndHere() {
return wordEndsHere;
}
public void markWordEndsHere() {
wordEndsHere = true;
}
@Override
public String toString() {
return Objects.toStringHelper(this)
.add("wordEndsHere", wordEndsHere)
.add("children", children)
.toString();
}
}
private final Node root = new Node(false);
public DictionaryTrie(String inputFilePath) throws IOException {
FileReader fr = new FileReader(inputFilePath);
BufferedReader br = new BufferedReader(fr);
try {
String line;
while ((line = br.readLine()) != null) {
line = line.toUpperCase();
Node node = root;
for (int i = 0; i < line.length(); ++i) {
char letter = line.charAt(i);
if (!Character.isUpperCase(letter)) {
break;
}
boolean lastCharacter = (i == line.length() - 1);
if (node.hasChildAtLetter(letter)) {
node = node.childForLetter(letter);
if (lastCharacter) {
node.markWordEndsHere();
}
} else {
Node child = new Node(lastCharacter);
node.addChildAtLetter(child, letter);
}
}
System.out.printf("Added %s\n", line);
}
} catch (IOException e) {
System.err.println("Error: " + e);
} finally {
br.close();
fr.close();
}
}
// nullable
private Node traverse(String word) {
Node node = root;
for (int i = 0; i < word.length(); ++i) {
char letter = word.charAt(i);
if (!Character.isUpperCase(letter)) {
return null;
}
if (node.hasChildAtLetter(letter)) {
node = node.childForLetter(letter);
} else {
return null;
}
}
return node;
}
public boolean containsWord(String word) {
Node node = traverse(word);
return node != null && node.doesWordEndHere();
}
public Set<Character> possibleSuccessorLetters(String prefix) {
Node node = traverse(prefix);
if (node == null) {
return ImmutableSet.of();
}
return node.childrenList();
}
}
|
