forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathAdd and Search Word.java
More file actions
executable file
·108 lines (88 loc) · 3.21 KB
/
Add and Search Word.java
File metadata and controls
executable file
·108 lines (88 loc) · 3.21 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
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
M
Trie结构, prefix tree的变形： '.'可以代替任何字符，那么就要iterate这个node所有的children.
节点里面有char, isEnd, HashMap<Character, TrieNode>
Build trie = Insert word:没node就加，有node就移动。
Search word:没有node就报错. 到结尾return true
这题因为'.'可以代替任何possible的字符，没一种都是一个新的path，所以recursive做比较好些。
(iterative就要queue了,麻烦点)
```
/*
Design a data structure that supports the following two operations: addWord(word) and search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or ..
A . means it can represent any one letter.
Example
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") // return false
search("bad") // return true
search(".ad") // return true
search("b..") // return true
Note
You may assume that all words are consist of lowercase letters a-z.
Tags Expand
Trie
*/
/*
Build the WordDictionary like a TrieTree.
Note: the '.' indicates any letter, which means we'd have to traverse through all possible letters in current level.
Only one of the returning search results needs to be true
Note:
TrieNode contains that char, boolean, and HashMap of children
*/
public class WordDictionary {
class TrieNode{
HashMap<Character, TrieNode> children;
boolean isEnd;
public TrieNode() {
this.children = new HashMap<Character, TrieNode>();
this.isEnd = false;
}
}
TrieNode root;
public WordDictionary(){
this.root = new TrieNode();
}
// Adds a word into the data structure.
public void addWord(String word) {
TrieNode node = root;
for (int i =0; i < word.length(); i++) {
char c = word.charAt(i);
if (!node.children.containsKey(c)) {
node.children.put(c, new TrieNode());
}
node = node.children.get(c);
}
node.isEnd = 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 searchHelper(root, word, 0);
}
public boolean searchHelper(TrieNode root, String word, int index) {
if (index == word.length()) {
return root.isEnd;
}
TrieNode node = root;
char c = word.charAt(index);
//border conditon:
if (node.children.containsKey(c)) {
return searchHelper(node.children.get(c), word, index + 1);
} else if (c == '.'){
for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
if (searchHelper(entry.getValue(), word, index + 1)) {
return true;
}
}
return false;
} else {
return false;
}
}
}
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");
```