-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathWordDictionary.java
More file actions
68 lines (63 loc) · 2.06 KB
/
Copy pathWordDictionary.java
File metadata and controls
68 lines (63 loc) · 2.06 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
public class WordDictionary{
private TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
// Adds a word into the data structure.
public void addWord(String word) {
TrieNode cur = root;
for(int i = 0; i < word.length(); i++){
if(cur.children[word.charAt(i) - 'a'] == null)
cur.children[word.charAt(i) - 'a'] = new TrieNode();
cur = cur.children[word.charAt(i) - 'a'];
}
cur.isLeaf = true;
}
// Returns if the word is in the data structure. A word could
// contain the dot character '.' to represent any one letter.
public boolean search(String word) {
return match(word, 0, root);
}
private boolean match(String word, int pos, TrieNode cur){
if(pos == word.length())
return cur.isLeaf;
char c = word.charAt(pos);
if(c == '.'){
for(int i = 0; i < 26; i++){
if(cur.children[i] != null && match(word, pos + 1, cur.children[i]))
return true;
}
return false;
} else {
if(cur.children[c - 'a'] != null)
return match(word, pos + 1, cur.children[c - 'a']);
else
return false;
}
}
public static void main(String[] argvs){
WordDictionary wd = new WordDictionary();
wd.addWord("at");
wd.addWord("and");
wd.addWord("an");
wd.addWord("add");
System.out.println(wd.search("a"));
System.out.println(wd.search(".at"));
wd.addWord("bat");
System.out.println(wd.search(".at"));
System.out.println(wd.search("an."));
System.out.println(wd.search("a.d."));
System.out.println(wd.search("b."));
System.out.println(wd.search("a.d"));
System.out.println(wd.search("."));
}
}
class TrieNode {
// Initialize your data structure here.
boolean isLeaf;
TrieNode[] children;
public TrieNode() {
isLeaf = false;
children = new TrieNode[26];
}
}