LeetCode208 实现Trie(前缀树)

链接: https://leetcode-cn.com/problems/implement-trie-prefix-tree

题意

尝试建立一个字典树,支持快速插入单词、查找单词、查找单词前缀的功能。

解法

学习一下新姿势字典树
需要使用到的是Trie节点,每个节点会有26个子节点,构成的一棵多叉树

由于一个英文单词的长度 n 通常在 10 以内,如果我们使用字典树,则可以在 O(n)近似 O(1)的时间内完成搜索,且额外开销非常小

本题中会建立一棵字典树,支持inser, search, startwith三种方法

代码

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
class TrieNode {
public:
TrieNode* childNode[26];
bool isVal;
TrieNode(): isVal(false) {
for (int i = 0; i < 26; i++) {
childNode[i] = nullptr;
}
}

};
class Trie {
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) { // 插入一个单词
int siz = word.size();
TrieNode* now = root;
for (int i = 0; i < siz; i++) {
int ch = word[i] - 'a';
if (!now -> childNode[ch]) {
now -> childNode[ch] = new TrieNode();
}
now = now -> childNode[ch];
}
now -> isVal = true;
}

bool search(string word) { // 搜索一个单词是否在字典树中
int siz = word.size();
TrieNode* now = root;
for (int i = 0; i < siz; i++) {
int ch = word[i] - 'a';
if (!now -> childNode[ch]) return false;
now = now -> childNode[ch];
}
return now ? now -> isVal : false;
}

bool startsWith(string prefix) { // 搜索一个前缀是否在字典树中出现过
int siz = prefix.size();
TrieNode* now = root;
for (int i = 0; i < siz; i++) {
int ch = prefix[i] - 'a';
if (!now -> childNode[ch]) return false;
now = now -> childNode[ch];
}
return true;
}
};