【设计-1】208.实现Trie (前缀树)

题目描述：

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True

解题思路：

方法一：字典树 (26 叉树)

核心思路：

Trie 的结构：

root
├── a
│ └── p
│ └── p
│ └── l
│ └── e (isEnd = true)
└── b
└── …

每个节点包含：

• children[26]：26 个子节点指针（对应 a-z）

• isEnd：是否是某个单词的结尾

操作逻辑：

代码实现：

class Trie {
private:
struct TrieNode {
TrieNode* children[26];
bool isEnd;

TrieNode() {
for (int i = 0; i < 26; i++) {
children[i] = nullptr;
}
isEnd = false;
}
};

TrieNode* root;

public:
Trie() {
root = new TrieNode();
}

void insert(string word) {
TrieNode* node = root;
for (char c : word) {
int index = c – 'a';
if (node->children[index] == nullptr) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->isEnd = true;
}

bool search(string word) {
TrieNode* node = root;
for (char c : word) {
int index = c – 'a';
if (node->children[index] == nullptr) {
return false;
}
node = node->children[index];
}
return node->isEnd;
}

bool startsWith(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
int index = c – 'a';
if (node->children[index] == nullptr) {
return false;
}
node = node->children[index];
}
return true;
}
};

复杂度分析：

设 L 是字符串长度。

关键细节：

1. 为什么用数组而不是哈希表？

TrieNode* children[26]; // 数组

• 数组访问 O(1)，比哈希表更快

• 题目限定小写字母，26 个足够

• 如果字符集更大，可以用 unordered_map<char, TrieNode*>

2. search 和 startsWith 的区别

// search: 必须是一个完整的单词
return node->isEnd;

// startsWith: 只要是前缀就行
return true;

关键：search 检查 isEnd，startsWith 不检查。

3. 为什么用 isEnd 标记？

因为一个单词可能是另一个单词的前缀：

插入 "apple" 后，再插入 "app"
如果不标记 isEnd，search("app") 无法区分 "app" 是完整单词还是 "apple" 的前缀

4. 内存泄漏问题

~Trie() {
deleteNode(root);
}

void deleteNode(TrieNode* node) {
for (int i = 0; i < 26; i++) {
if (node->children[i]) {
deleteNode(node->children[i]);
}
}
delete node;
}

LeetCode 上不要求，但实际工程中需要释放内存。

方法二：哈希表

为什么用哈希表？

优势：如果字符集很大（如 Unicode），或者子节点很稀疏，哈希表更省空间。

代码实现：

class Trie {
private:
struct TrieNode {
unordered_map<char, TrieNode*> children; // 哈希表存子节点
bool isEnd;

TrieNode() : isEnd(false) {}
};

TrieNode* root;

public:
Trie() {
root = new TrieNode();
}

void insert(string word) {
TrieNode* node = root;
for (char c : word) {
// 如果子节点不存在，创建
if (node->children.find(c) == node->children.end()) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->isEnd = true;
}

bool search(string word) {
TrieNode* node = root;
for (char c : word) {
if (node->children.find(c) == node->children.end()) {
return false;
}
node = node->children[c];
}
return node->isEnd;
}

bool startsWith(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
if (node->children.find(c) == node->children.end()) {
return false;
}
node = node->children[c];
}
return true;
}
};

更简洁的写法（用 count）：

void insert(string word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c)) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->isEnd = true;
}

bool search(string word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c)) return false;
node = node->children[c];
}
return node->isEnd;
}

bool startsWith(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
if (!node->children.count(c)) return false;
node = node->children[c];
}
return true;
}

具体过程示例：

插入 "apple" 后：

root
└── children['a'] → node_a
└── children['p'] → node_p1
└── children['p'] → node_p2
└── children['l'] → node_l
└── children['e'] → node_e (isEnd=true)

哈希表只存实际存在的字符，不像数组要开 26 个位置。

复杂度分析：

设 L 是字符串长度。

空间复杂度对比：

• 数组：O(总字符数 × 26)

• 哈希表：O(总字符数)

关键细节：

1. find vs count vs []

注意：children[c] 在键不存在时会插入一个默认值（nullptr），可能改变哈希表大小。

2. 为什么哈希表更省空间？

• 数组：每个节点固定 26 个指针，共 26 × 8 = 208 字节

• 哈希表：只存实际存在的子节点，稀疏时节省大量空间

3. 什么时候用数组，什么时候用哈希表？

数组 vs 哈希表对比：