题目
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary ：
- WordDictionary() 初始化词典对象
- void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
- bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 ‘.’ ，每个 . 都可以表示任何一个字母。
示例
示例一：
输入：
[“WordDictionary”,”addWord”,”addWord”,”addWord”,”search”,”search”,”search”,”search”]
[[],[“bad”],[“dad”],[“mad”],[“pad”],[“bad”],[“.ad”],[“b..”]]
输出：
[null,null,null,null,false,true,true,true]
解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord(“bad”);
wordDictionary.addWord(“dad”);
wordDictionary.addWord(“mad”);
wordDictionary.search(“pad”); // return False
wordDictionary.search(“bad”); // return True
wordDictionary.search(“.ad”); // return True
wordDictionary.search(“b..”); // return True
提示
- 1 <= word.length <= 500
- addWord 中的 word 由小写英文字母组成
- search 中的 word 由 ‘.’ 或小写英文字母组成
- 最多调用 50000 次 addWord 和 search
解题
本题要进行插入和搜索，可以使用前缀树来实现，前缀树类实现如下：
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
| class Trie{
private Trie[] children;
private boolean isEnd;
public Trie(){
children = new Trie[26];
isEnd = false;
}
public void insert(String word){
Trie node = this;
for (int i=0; i<word.length();i++){
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index]==null){
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public Trie[] getChildren(){
return children;
}
public boolean isEnd(){
return isEnd;
}
}
|
深度优先遍历字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
private boolean dfs(String word, int index, Trie node){
if (index==word.length()){
return node.isEnd();
}
char ch = word.charAt(index);
if (Character.isLetter(ch)){
int childIndex = ch - 'a';
Trie child = node.getChildren()[childIndex];
if (child!=null && dfs(word,index+1,child)){
return true;
}
}else {
for (int i = 0; i < 26; i++) {
Trie child = node.getChildren()[i];
if (child!=null&&dfs(word,index+1,child)){
return true;
}
}
}
return false;
}
|
组合起来：
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
| class WordDictionary {
private Trie root;
public WordDictionary() {
root = new Trie();
}
public void addWord(String word) {
root.insert(word);
}
public boolean search(String word) {
return dfs(word, 0, root);
}
private boolean dfs(String word, int index, Trie node){
if (index==word.length()){
return node.isEnd();
}
char ch = word.charAt(index);
if (Character.isLetter(ch)){
int childIndex = ch - 'a';
Trie child = node.getChildren()[childIndex];
if (child!=null && dfs(word,index+1,child)){
return true;
}
}else {
for (int i = 0; i < 26; i++) {
Trie child = node.getChildren()[i];
if (child!=null&&dfs(word,index+1,child)){
return true;
}
}
}
return false;
}
}
class Trie{
private Trie[] children;
private boolean isEnd;
public Trie(){
children = new Trie[26];
isEnd = false;
}
public void insert(String word){
Trie node = this;
for (int i=0; i<word.length();i++){
char ch = word.charAt(i);
int index = ch - '';
if (node.children[index]==null){
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public Trie[] getChildren(){
return children;
}
public boolean isEnd(){
return isEnd;
}
}
|