208. 实现 Trie(前缀树)
一句话套路26 叉树 + isEnd 区分词与前缀
题目描述
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
提示:
1 <= word.length, prefix.length <= 2000word和prefix仅由小写英文字母组成insert、search和startsWith调用次数 总计 不超过3 * 104次
思路
空间
O(所有前缀结点数)结构
每个结点存 26 个孩子指针 + 一个「结束标志」。
search 走到底且 isEnd;startsWith 只要走到底 —— 两者的区别就是 end 标志。
取舍
数组孩子表查询最快但费空间(26 指针/结点);
字符集大或稀疏时用 unordered_map 或「排序后二分」的孩子列表。
应用
单词搜索 Q211/Q212、敏感词过滤、IP 路由最长前缀匹配。
图解
字符串
banana(来自本仓库测试数据,下标从 0 开始)C++17 题解
namespace lc0208 {
class Trie {
public:
Trie() = default;
~Trie() {
for (Trie* c : kids_) delete c;
}
Trie(const Trie&) = delete;
Trie& operator=(const Trie&) = delete;
void insert(const string& word) {
Trie* cur = this;
for (char ch : word) {
int i = ch - 'a';
if (!cur->kids_[i]) cur->kids_[i] = new Trie();
cur = cur->kids_[i];
}
cur->isEnd_ = true;
}
bool search(const string& word) const {
const Trie* n = walk(word);
return n && n->isEnd_;
}
bool startsWith(const string& prefix) const { return walk(prefix) != nullptr; }
private:
std::array<Trie*, 26> kids_{}; // {} -> 全部初始化为 nullptr
bool isEnd_ = false;
Trie* walk(const string& s) {
Trie* cur = this;
for (char ch : s) {
int i = ch - 'a';
if (!cur->kids_[i]) return nullptr;
cur = cur->kids_[i];
}
return cur;
}
const Trie* walk(const string& s) const {
const Trie* cur = this;
for (char ch : s) {
int i = ch - 'a';
if (!cur->kids_[i]) return nullptr;
cur = cur->kids_[i];
}
return cur;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0208::Trie t;
t.insert("apple");
CHECK_TRUE(t.search("apple"));
CHECK_FALSE(t.search("app")); // 前缀存在,但不是完整词
CHECK_TRUE(t.startsWith("app"));
t.insert("app");
CHECK_TRUE(t.search("app")); // 插入后才成为完整词
CHECK_FALSE(t.startsWith("ban"));
CHECK_FALSE(t.search("")); // 空串不是任何已插入的词
CHECK_TRUE(t.startsWith("")); // 但空前缀恒成立
t.insert("banana");
CHECK_TRUE(t.search("banana"));
CHECK_FALSE(t.search("ban"));