05 August 2008
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 1
a-z
1
.
1
.
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 1
a-z
设计一个数据结构，实现 add 方法添加字符串，search 查找字符串，所查找的字符串可能含有 ‘.’ ，代表任意的一个字符。
暴力方法，可以用 HashSet 存入所有的字符串。当查找字符串的时候，我们首先判断 set 中是否存在，如果存在的话直接返回 true 。不存在的话，因为待查找的字符串中可能含有 . ，接下来我们需要遍历 set ，一个一个的进行匹配。
优化的办法是用Trie，通过208题实现的前缀树进行存储，这样查找字符串就不用依赖于字符串的数量了， 对于字符串中的 1
.
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
class WordDictionary {
/**
Trie的实现，不用实现insert(),search()和startWith()
*/
class TrieNode {
TrieNode[] children;
boolean flag;
public TrieNode() {
children = new TrieNode[26];
flag = false;
for (int i = 0; i < 26; i++) {
children[i] = null;
}
}
}
TrieNode root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) { // 将新来的单词存入Trie中
char[] array = word.toCharArray();
TrieNode cur = root;
for (int i = 0; i < array.length; i++) {
// 当前孩子是否存在
if (cur.children[array[i] - 'a'] == null) {
cur.children[array[i] - 'a'] = new TrieNode();
}
cur = cur.children[array[i] - 'a'];
}
// 当前节点代表结束
cur.flag = 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 recursion(word, root);
}
private boolean recursion(String word, TrieNode root) {
char[] array = word.toCharArray();
TrieNode cur = root;
for (int i = 0; i < array.length; i++) {
// 对于 . , 递归的判断所有不为空的孩子
if(array[i] == '.'){
for(int j = 0; j < 26; j++){
if(cur.children[j] != null){
if(recursion(word.substring(i + 1),cur.children[j])){
return true;
}
}
}
return false;
}
// 不含有当前节点
if (cur.children[array[i] - 'a'] == null) {
return false;
}
cur = cur.children[array[i] - 'a'];
}
// 当前节点是否为是某个单词的结束
return cur.flag;
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
使用正则表达式，Python解法可以AC， 用 1
#
1
# + word + #
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
import re
class WordDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.words = '#'
def addWord(self, word: str) -> None:
"""
Adds a word into the data structure.
"""
self.words += word + '#'
def search(self, word: str) -> bool:
"""
Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
"""
return bool(re.search('#' + word + '#', self.words))
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)