LeetCode - Add and Search Word Data Structure Design
Problem description
Design a data structure that supports the following two operations:
1
2
void addWord(word)
bool 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:
1
2
3
4
5
6
7
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
- You may assume that all words are consist of lowercase letters a-z.
Analysis
The first idea is to use prefix trie to do this.
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
class WordDictionary {
Node root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new Node('*');
}
/** Adds a word into the data structure. */
public void addWord(String word) {
Node p = root;
for (char c:word.toCharArray()){
if (!p.children.containsKey(c)){
p.children.put(c, new Node(c));
}
p = p.children.get(c);
}
p.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 search(word, 0, root);
}
boolean search(String word, int index, Node p){
char[] chars = word.toCharArray();
for (int i = index; i< chars.length; i++){
char c = chars[i];
if (!p.children.containsKey(c) && c != '.'){
return false;
}
else if (c == '.'){
for (Node node:p.children.values()){
if (search(word, i+1, node)){
return true;
}
}
return false;
}
else{
p = p.children.get(c);
}
}
return p.isEnd;
}
class Node {
char val;
HashMap<Character, Node> children;
boolean isEnd;
public Node(char c){
val = c;
children = new HashMap<>();
isEnd = false;
}
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/