算法实战：课程表环检测与 Trie 前缀树实现

4. 复杂度分析

• 时间复杂度：O(V + E)。
  • V 是课程数（节点），E 是依赖关系数（边）。
  • DFS 过程中，每个节点最多由 0 变 1 再变 2 一次，每条边最多被检查一次。
• 空间复杂度：O(V + E)。
  • 邻接表 g 需要 O(V + E) 的空间。
  • 标记数组 sign 需要 O(V) 的空间。
  • 递归栈的深度最大为 O(V)。

二、实现 Trie (前缀树/字典树)

1. 题目核心：空间换时间

Trie 是一种专门处理字符串匹配的树形结构。

• 特点：每个节点代表一个字符的位置，通常有 26 个分支（对应 'a'-'z'）。
• 优势：利用字符串的公共前缀来减少查询时间。查找 "apple" 和 "app" 会走同一条路。

2. 优化思路：万能的 Find 函数

题目要求实现 search（查完整单词）和 startsWith（查前缀）。为了代码复用，我们设计一个辅助函数 find(word)，用返回值区分三种状态：

• 返回 0：路断了，不存在。
• 返回 1：路通了，但没遇到结束标记，说明前缀存在。
• 返回 2：路通了，且遇到了 end=true，说明完整单词存在。

3. 代码实现 (C++)

关于析构函数：在 LeetCode 刷题中，为了代码简洁和运行速度，通常省略手动 delete 内存的步骤（程序结束时系统会统一回收）。但在实际工程开发中，必须写析构函数来防止内存泄漏。

struct Node {
    Node* son[26]{}; // 26 个分支，代表 'a'-'z'，初始化为空指针
    bool end = false; // 标记：走到这里是否是一个完整的单词
};

class Trie {
    // 根节点，初始为空
    Node* root = new Node();

    // 【核心逻辑】万能查找函数
    // 返回值含义：0=不存在，1=前缀存在，2=完整单词存在
    int find(string word) {
        Node* cur = root;
        for (char c : word) {
            c -= 'a'; // 将字符映射为 0-25 的索引
            // 如果路断了 (空指针)，直接返回 0
            if (cur->son[c] == nullptr) {
                return 0;
            }
            cur = cur->son[c]; // 继续向下走
        }
        // 循环走完，说明路通了。
        // 检查 end 标记：如果是 true 返回 2，否则返回 1
        return cur->end ? 2 : 1;
    }

public:
    // 构造函数
    Trie() {}

    // 插入单词：类似'造路'的过程
    void insert(string word) {
        Node* cur = root;
        for (char c : word) {
            c -= 'a';
            // 如果前方没路，就 new 一个新节点出来
            if (cur->son[c] == nullptr) {
                cur->son[c] = new Node();
            }
            cur = cur->son[c];
        }
        // 单词走完，打上结束标记
        cur->end = true;
    }

    // 查找完整单词：要求 find 返回 2
    bool search(string word) {
        return find(word) == 2;
    }

    // 查找前缀：只要 find 返回不是 0 (即 1 或 2 都可以)
    bool startsWith(string prefix) {
        return find(prefix) != 0;
    }
};

4. 复杂度分析

假设我们要插入或查询的字符串长度为 L。

• 时间复杂度：O(L)。
  • 无论是插入、查找还是前缀匹配，我们都只需要遍历一次字符串，树的高度由字符串长度决定，与字典中存了多少个词无关。
• 空间复杂度：O(N * L * 26)。
  • 最坏情况下（没有公共前缀），每个字符都需要一个新节点。
  • N 是单词数量，L 是平均长度，26 是字符集大小。
  • 实际应用中，由于前缀复用，真实空间占用会远小于最坏情况。

总结

• 课程表教会了我们如何用 DFS + 三色标记法 解决图的环检测问题。
• Trie 教会了我们如何用 树形结构 + 指针 极其高效地处理字符串前缀问题。