LeetCode 208. 实现 Trie (前缀树) C++ 题解

LeetCode 208. 实现 Trie (前缀树) | C++ 字典树题解

📌 题目描述

题目级别：中等

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) 的核心原理

字典树的核心思想是空间换时间，利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

1. 节点结构设计

Trie 的每个节点并不直接保存整个字符串，而是保存单个字符的映射关系。 在本题中（仅包含小写字母），每个节点需要包含两个信息：

• son[30]：一个指针数组，用于指向后续的子节点（这里开辟大小为 30 的数组，足以容纳 26 个小写字母，且能防溢出）。
• ed（isEnd）：一个布尔标志位，标记当前节点是否是某个单词的结尾。

2. 核心操作解析

• 插入 (insert)：从根节点出发，遍历要插入单词的每一个字符。将字符转化为索引（c - 'a'），如果对应的子节点不存在，就 new 一个新节点。遍历结束后，将最后停留的节点的 ed 标记为 true。
• 精准查找 (search)：同样从根节点出发，按字符顺藤摸瓜。如果中途某个字符对应的子节点为空，说明单词不存在，直接返回 false。如果顺利走完单词的每个字符，还要检查最终停留节点的 ed 是否为 true（因为可能只是别的单词的一个前缀，而不是独立的单词）。
• 前缀查找 (startsWith)：逻辑与 search 完全一致，唯一的区别是：只要能顺利走完前缀的所有字符，就直接返回 true，不需要关心 ed 的状态。

---

💻 C++ 代码实现

class Trie {
public:
    // 定义 Trie 的节点结构
    struct Node {
        bool ed; 
        Node *son[]; 
        () {
            ed = ;
            ( i = ; i < ; i++) son[i] = ;
        }
    } *root;

    
    () { root =  (); }

    
    {
         p = root;
        ( c : word) {
             u = c - ; 
            (p->son[u] == ) p->son[u] =  (); 
            p = p->son[u]; 
        }
        p->ed = ; 
    }

    
    {
         p = root;
        ( c : word) {
             u = c - ;
            (p->son[u] == )  ; 
            p = p->son[u];
        }
         p->ed; 
    }

    
    {
         p = root;
        ( c : prefix) {
             u = c - ;
            (p->son[u] == )  ; 
            p = p->son[u];
        }
         ; 
    }
};