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
·181 lines (157 loc) · 5.39 KB
/
Add and Search Word.java
File metadata and controls
executable file
·181 lines (157 loc) · 5.39 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
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
M
1520491896
tags: Backtracking, Design, Trie
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
*/
/*
Thougths:
Use Trie to store the letters and mark end letter with end = true
Trie structure:
class TrieNode {
HashMap<Character, TrieNode> map;
boolean isEnd;
}
During search, when facing '.', try all possible characters with the given TrieNode.map
*/
class WordDictionary {
class TrieNode {
HashMap<Character, TrieNode> map;
boolean end;
TrieNode() {
this.map = new HashMap<>();
this.end = false;
}
public HashMap<Character, TrieNode> getMap() {
return map;
}
public boolean isEnd() {
return this.end;
}
}
TrieNode root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
char[] arr = word.toCharArray();
TrieNode node = root;
for (char c : arr) {
HashMap<Character, TrieNode> map = node.getMap();
if (!map.containsKey(c)) {
map.put(c, new TrieNode());
}
node = map.get(c);
}
node.end = 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);
HashMap<Character, TrieNode> map = node.getMap();
if (map.containsKey(c)) {
return searchHelper(map.get(c), word, index + 1);
} else if (c == '.') {
for (Map.Entry<Character, TrieNode> entry : map.entrySet()) {
if (searchHelper(entry.getValue(), word, index + 1)) {
return true;
}
}
return false;
}
return false;
}
}
/*
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");
```