208. 实现 Trie (前缀树)
4 min
题目
解法：前缀树
思路
核心思想是前缀树，通过树形结构共享字符串前缀实现高效存储检索。每个节点代表一个字符，路径表示前缀，isEnd 标记单词结尾。
正确性基于路径唯一性：插入和查询遵循相同字符路径规则，确保数据一致性。插入时按需创建节点，查询时沿路径遍历，若路径存在且 isEnd 为真则命中，否则失败。
- Step 1: 定义 TrieNode 结构，包含 26 个子节点指针和 isEnd 标志
- Step 2: insert 遍历单词字符，创建缺失子节点，最后标记 isEnd=true
- Step 3: search 遍历单词字符，路径中断返回 false，否则返回 isEnd
- Step 4: startsWith 遍历前缀字符，路径中断返回 false，否则返回 true
复杂度
- 时间复杂度: ，其中 L 为单词或前缀长度。每次操作需遍历字符串每个字符，每步操作耗时 。
- 空间复杂度: ，N 为插入单词数，L 为平均长度。最坏情况下每个单词都无共享前缀，需 个节点。
代码
class Trie {
private:
struct TrieNode {
TrieNode* children[26];
bool isEnd;
TrieNode() : isEnd(false) {
for (int i = 0; i < 26; i++) children[i] = nullptr;
}
};
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* curr = root;
for (char c : word) {
int idx = c - 'a';
if (!curr->children[idx]) {
curr->children[idx] = new TrieNode();
}
curr = curr->children[idx];
}
class Trie {
private:
struct TrieNode {
TrieNode* children[26];
bool isEnd;
TrieNode() : isEnd(false) {
for (int i = 0; i < 26; i++) children[i] = nullptr;
}
};
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* curr = root;
for (char c : word) {
int idx = c - 'a';
if (!curr->children[idx]) {
curr->children[idx] = new TrieNode();
}
curr = curr->children[idx];
}
curr->isEnd = true;
}
bool search(string word) {
TrieNode* curr = root;
for (char c : word) {
int idx = c - 'a';
if (!curr->children[idx]) {
return false;
}
curr = curr->children[idx];
}
return curr->isEnd;
}
bool startsWith(string prefix) {
TrieNode* curr = root;
for (char c : prefix) {
int idx = c - 'a';
if (!curr->children[idx]) {
return false;
}
curr = curr->children[idx];
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/