HHot 100C++ 图解

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 <= 2000
  • word 和 prefix 仅由小写英文字母组成
  • insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

思路

空间O(所有前缀结点数)

结构

每个结点存 26 个孩子指针 + 一个「结束标志」。

search 走到底且 isEnd;startsWith 只要走到底 —— 两者的区别就是 end 标志。

取舍

数组孩子表查询最快但费空间(26 指针/结点);

字符集大或稀疏时用 unordered_map 或「排序后二分」的孩子列表。

应用

单词搜索 Q211/Q212、敏感词过滤、IP 路由最长前缀匹配。

图解

b 0 a 1 n 2 a 3 n 4 a 5
字符串 banana(来自本仓库测试数据,下标从 0 开始)

C++17 题解

src/09_graph.cpp51 行
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;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q208_implement_trie13 行
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"));

↑↓ 选择↵ 打开/ 随时唤起