📅 2026-06-27

Saturday, June 27, 2026

5 sections ~15 min read 🌏 Bilingual 中/EN
🏗️ System Design 💻 Algorithms 🗣️ Soft Skills 🤖 AI 🔬 Deep Dive
← 2026-06-26 📂 All Days 2026-06-28 →

Saturday deep dive day — see 2026-06-27-deepdive.md

Saturday deep dive day — see 2026-06-27-deepdive.md

Saturday deep dive day — see 2026-06-27-deepdive.md

Saturday deep dive day — see 2026-06-27-deepdive.md

🔬 Saturday Deep Dive: 前缀树 & 通配符搜索 — Design Add and Search Words (15 min read)

📊 NeetCode: 61/150 · SysDesign: 60/40 · Behavioral: 60/40 · Frontend: 37/50 · AI: 30/30

🔥 Keep the streak alive!

Overview / 概述

中文：

前缀树（Trie）是一种树形数据结构，专为字符串的前缀操作而生。它的核心思想简单而优雅：把每个字符当成树的一层，共享公共前缀。插入一百万个以 "inter" 开头的单词？只需在树里存一个 "inter" 前缀节点，而不是一百万个独立字符串的副本。

今天的题目 LeetCode #211（Design Add and Search Words Data Structure）在标准 Trie 的基础上加了一个转折：. 可以匹配任意字符。这把一个 O(L) 的查询变成了需要回溯的 DFS，让问题从"简单前缀匹配"升级为"带通配符的模式匹配"。

English:

A Trie is a tree structure built for prefix operations. Every character becomes a level in the tree; common prefixes are shared. The twist in LeetCode #211: the . wildcard can match any single character, turning a straightforward O(L) lookup into a DFS with backtracking. Understanding this jump — from exact match to pattern match — is the core insight of this deep dive.

Why it matters: Tries are everywhere in production — autocomplete, spell checkers, IP routing tables, search indexing. The wildcard variant maps directly to regex engines, DNS glob matching, and file system glob patterns.

Part 1: Theory / 理论基础 (5 min)

Trie 的结构

中文：

插入 "bad", "dad", "mad", "pad" 后的 Trie：

          root
        /  |  \  \
       b   d   m   p
       |   |   |   |
       a   a   a   a
       |   |   |   |
      [d] [d] [d] [d]
       *   *   *   *     (* = is_end = True)

每个节点包含：

  1. children: dict[str, TrieNode] — 子节点映射（26 个字母 → 最多 26 个孩子）
  2. is_end: bool — 是否是某个单词的终点

English:

Each node doesn't store a character — it IS a character in its parent's edge. Nodes only store:

  • children: which characters follow this prefix
  • is_end: does a complete word terminate here

为什么 . 通配符要用 DFS + 回溯？

中文：

正常搜索 "bad"：

root → children['b'] → children['a'] → children['d'] → is_end? True ✓

搜索 "b.d"（. 匹配任意字符）：

root → children['b'] → ???

到了 b 节点，. 可以匹配 b 的任何子节点。我们不知道该走哪条路，所以必须把 b 的所有子节点都尝试一遍，看哪条路最终能走到 d 的 is_end。

这就是回溯的本质：枚举所有可能的分支，剪掉死路，直到找到答案或穷举所有路径。

English:

Wildcards force us to explore multiple branches simultaneously. When we hit `.`, we can't prune — we must try every child. This is classic **backtracking**: branch → explore → backtrack if failure. The key insight is recognizing that `.` converts a lookup from a single path traversal to a DFS over a subtree.

时间复杂度分析

操作时间复杂度空间复杂度
addWord(word)O(L)O(L) 最坏情况新建 L 个节点
search(word) — 无通配符O(L)O(1) 栈空间
search(word) — 全 .O(N) N=所有节点数O(L) DFS 栈深度

最坏情况：搜索 "..." 且字典里有 10 万个 3 字母单词 → 遍历整个 Trie。

Part 2: Step-by-Step Implementation / 一步一步实现 (8 min)

朴素实现 → 优化过程

中文解题思路：

方法一：暴力（不用 Trie）

把所有单词存进 list，搜索时用 re.match。

  • 时间：O(N·L) 每次搜索
  • 空间：O(N·L)
  • 不合格：面试官要的就是 Trie

方法二：标准 Trie

能高效处理精确匹配，但 . 通配符需要额外处理。

方法三：Trie + DFS 回溯（最优解）

English approach: Build a standard Trie. For search, recurse through the Trie character by character. When we hit ., recurse into ALL children and return True if any subtree returns True.

完整实现代码

class TrieNode:
    def __init__(self):
        # Use a dict for sparse storage (not all 26 letters used)
        # Alternative: self.children = [None] * 26 (array-based, cache-friendly)
        self.children: dict[str, 'TrieNode'] = {}
        self.is_end: bool = False  # True if a complete word ends here


class WordDictionary:
    """
    LeetCode #211: Design Add and Search Words Data Structure
    
    Supports:
      - addWord(word): insert exact word
      - search(word): match with '.' as wildcard for any single char
    
    Key insight: '.' wildcards require DFS + backtracking across all children.
    """

    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        """
        Insert word into the Trie.
        Time: O(L) where L = len(word)
        Space: O(L) worst case (all new characters)
        """
        node = self.root
        for ch in word:
            # Create child node if this character path doesn't exist yet
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        # Mark the end of this word
        node.is_end = True

    def search(self, word: str) -> bool:
        """
        Search for word, where '.' matches any single character.
        Time: O(L) best case (no wildcards), O(N) worst case (all wildcards)
        Space: O(L) recursion stack depth
        """
        return self._dfs(word, 0, self.root)

    def _dfs(self, word: str, idx: int, node: TrieNode) -> bool:
        """
        Recursive DFS through the Trie.
        
        Args:
            word: the search pattern
            idx: current position in word (which character we're matching)
            node: current Trie node we're at
        
        Returns:
            True if word[idx:] matches any path from node
        """
        # Base case: consumed all characters
        # Check if we're at a valid word ending
        if idx == len(word):
            return node.is_end

        ch = word[idx]

        if ch == '.':
            # Wildcard: try EVERY child node
            # Return True if ANY child path leads to a complete match
            for child in node.children.values():
                if self._dfs(word, idx + 1, child):
                    return True  # Found a match — no need to continue
            return False  # No child path matched

        else:
            # Exact character match
            if ch not in node.children:
                return False  # Dead end — this path doesn't exist
            # Recurse into the matching child
            return self._dfs(word, idx + 1, node.children[ch])


# ============================================================
# Usage Example
# ============================================================
if __name__ == "__main__":
    wd = WordDictionary()
    wd.addWord("bad")
    wd.addWord("dad")
    wd.addWord("mad")

    print(wd.search("pad"))   # False — 'p' not in root's children
    print(wd.search("bad"))   # True  — exact match
    print(wd.search(".ad"))   # True  — '.' matches 'b', 'd', or 'm'
    print(wd.search("b.."))   # True  — 'b' → any → any → is_end
    print(wd.search("b.x"))   # False — 'b' → any → no 'x' exists

迭代版本（避免递归栈溢出）

中文： 对于极深的 Trie（单词很长），递归可能栈溢出。生产环境可用显式栈模拟 DFS：

def search_iterative(self, word: str) -> bool:
    """
    Iterative DFS using an explicit stack.
    Stack stores (node, idx) pairs — current node and word index.
    Avoids Python's recursion limit for very long words.
    """
    from collections import deque
    
    # Stack of (current_node, current_index_in_word)
    stack = [(self.root, 0)]
    
    while stack:
        node, idx = stack.pop()
        
        # Consumed all characters — check if valid word end
        if idx == len(word):
            if node.is_end:
                return True
            continue
        
        ch = word[idx]
        
        if ch == '.':
            # Push ALL children with next index
            for child in node.children.values():
                stack.append((child, idx + 1))
        else:
            # Push only the matching child (if it exists)
            if ch in node.children:
                stack.append((node.children[ch], idx + 1))
    
    return False

下一题预告：Word Search II (#212) — Trie + Grid DFS

中文： 掌握了今天的 Trie 后，#212 Word Search II 就是把 Trie 和 2D 网格 DFS 结合：

# 核心思路：把所有单词建成 Trie，然后在 grid 上 DFS
# 每走一步，同时在 Trie 中推进 —— 提前剪枝不存在的前缀
def findWords(board, words):
    # 1. 把所有单词插入 Trie
    # 2. 从 grid 每个格子出发，DFS
    # 3. DFS 同时追踪 Trie 节点：
    #    - 当前字符不在 node.children → 剪枝
    #    - node.is_end → 找到一个词
    pass  # Full implementation in Monday's newsletter

Part 3: Edge Cases & Gotchas / 边界情况 (2 min)

中文：

  1. 空字符串搜索 — search("") 应该返回 root.is_end。如果你调用过 addWord("")（空字符串），则 root.is_end = True。很多实现忘记处理这个。
  1. 纯通配符搜索 — search("...") 会遍历整个 Trie。最坏时间 O(N·L)。面试中提到这个。
  1. is_end 覆盖问题 — 插入 "app" 和 "apple"：节点 p（第三个字符）的 is_end = True，同时它还有子节点 l。遍历时不要因为到达 is_end 节点就停止向下查找——只有当 idx == len(word) 时才检查 is_end。
  1. 大小写敏感 — 标准实现区分大小写。生产环境通常 word.lower() 标准化。
  1. 并发写入 — 多线程同时 addWord 会产生竞争条件。生产中需要读写锁（RWLock）或 lock-free Trie（用数组 + CAS）。

English:

  • Empty string: search("") hits base case immediately; returns root.is_end.
  • All wildcards: degenerate to full Trie traversal — mention this complexity to interviewers.
  • is_end coexisting with children: a node can be both a word terminal and an internal node (e.g., "app" inside "apple"). The code handles this correctly because we only check is_end at idx == len(word).
  • Duplicate inserts: inserting the same word twice is idempotent — the second insert just walks existing nodes and sets is_end = True again.

Part 4: Real-World Application / 实际应用 (2 min)

中文：

1. 搜索引擎自动补全

Google Suggest、IDE 的代码补全都是 Trie 的直接应用。Trie 支持 O(L) 的前缀查询（L = 输入长度），无论字典里有多少词。加上频率权重 → 变成带优先队列的 "prefix + top-K" 系统。

2. 网络路由：IP 前缀匹配

路由表用 Trie 存 IP 前缀（CIDR）。查找目标 IP 时，做最长前缀匹配（Longest Prefix Match）。网络设备里的 Trie 用二进制（bit-level），每层代表一位，深度最多 32（IPv4）或 128（IPv6）。

3. 拼写检查 & 模糊匹配

通配符搜索 → 自然扩展为编辑距离搜索（Levenshtein）：在 Trie 上 DFS 时携带一个 "剩余错误次数"，允许插入/删除/替换。生产中的拼写检查引擎（Hunspell、SymSpell）正是这个思路。

4. DNS 通配符解析

DNS 记录如 *.example.com 匹配任何子域。DNS 服务器内部用 Trie 存储域名（注意：域名从右到左匹配），. 就是通配符。

English summary: Tries underpin autocomplete, IP routing (CIDR longest prefix match), spell checkers with edit-distance tolerance, and DNS wildcard resolution. The wildcard variant you built today maps directly to glob pattern matchers in shells (ls .py), regex engines for simple patterns, and configuration systems that support in key paths.

Part 5: Interview Simulation / 面试模拟 (3 min)

中文：模拟面试追问（FAANG Staff 级别）

Q1: 如果字典里有 100 万个单词，每个长度最多 20，Trie 的内存占用大概多少？

A: 最坏情况（无共享前缀）：100万 × 20 节点 × 每节点约 200 字节（Python dict overhead）= ~4GB，不可接受。优化：

  • 用数组代替 dict（children = [None] * 26），每节点 ~400 字节 → 约 8GB（更差）
  • 实际中有大量前缀共享，内存显著减少
  • 生产方案：压缩 Trie（Patricia/Radix Trie）合并单链节点，节省 80%+ 内存

Q2: . 通配符最坏情况是什么？如何优化？

A: 所有字符都是 .，且 Trie 极宽（每节点有 26 个子节点）→ 遍历整个 Trie，O(26^L)。

优化：

  1. 限制最大通配符数（业务层约束）
  2. 预计算反向索引（字符 → 含该字符单词列表）
  3. Bit-parallel matching（SIMD 加速）

Q3: 如果要支持前缀搜索（"返回所有以 'pre' 开头的单词"），如何修改？

A: 走到前缀的末尾节点，然后 DFS 收集所有 is_end = True 的路径。时间 O(P + R) 其中 P=前缀长度，R=结果数量。可以在每个节点额外维护 word_count（子树中单词总数）用于剪枝或排序。

Q4: 如何支持 deleteWord(word)？

A: 递归删除：从叶节点向上，如果该节点没有其他子节点且 is_end = False，则从父节点的 children 中移除。注意：如果单词是另一个单词的前缀（"app" in "apple"），只需把末尾节点的 is_end 设为 False，不删节点。

Q5: 这道题在 Python 里有什么陷阱？

A: Python 的 dict lookup 是 O(1) 均摊但常数大。对于高性能场景，用 children = [None] * 26 + 字符 ord 映射更快（缓存友好）。另外，Python 默认递归限制是 1000，Trie 深度超过时需要 sys.setrecursionlimit 或改用迭代版本。

English version (quick):

  1. Memory at scale? 1M words × 20 chars × 200B/node = ~4GB worst case. Production uses Radix/Patricia Tries (compressed) — merge single-child chains, save 80%+ memory.
  1. Worst case for wildcards? All . pattern + 26-ary Trie → O(26^L). Mitigate with: wildcard count limits, bitset intersection, or precomputed inverted indices by character.
  1. Prefix listing (autocomplete)? Walk to prefix end node, DFS to collect all is_end paths. Add word_count per node for ranking/pruning.
  1. Delete support? Recursive: unset is_end, then walk back up deleting leaf nodes with no children. Stop if a node serves as prefix for another word.
  1. Python-specific gotchas? Dict vs array children (cache locality), recursion limit at depth > 1000, defaultdict vs explicit dict (defaultdict adds overhead for missing key queries).

🔗 LeetCode: https://leetcode.com/problems/design-add-and-search-words-data-structure/

📹 NeetCode: https://neetcode.io/problems/design-word-search-data-structure

⏭️ Next up: #212 Word Search II (Hard) — Trie meets 2D backtracking

🔬 Saturday Deep Dive — byte-by-byte Day 76