Pinterest Trie 自动补全：Add、Search、Delete 与前缀建议

题目重点：Senior MLE 题目明确 Trie search autocomplete，另一帖提到 add/search/delete；本文给出可独立验证的精确词和前缀训练接口。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练版字典保存字符串集合；add 重复词幂等，search 只查完整词，delete 不存在词返回 false；autocomplete(prefix,k) 按词典序返回至多 k 个词。
题目没有公开建议排序规则、词频、个性化、Unicode 规范化或并发要求；词典序仅是可验证训练并列规则。
空字符串可作为完整词存于 root，空前缀可返回全局词典序前 k 项。

解题路线

每个 TrieNode 将 children 与 terminal 建成实例属性，避免不同节点共享 class-level 字典导致分支串联；沿字符路径 add/search 都 O(L)。
删除时记录父节点路径，取消 terminal 后从叶向上剪掉无单词经过的空节点；若节点仍有子分支，不能删除整个前缀。
自动补全先走到 prefix 节点，再 DFS 枚举该子树；每层按字符顺序压栈，前 k 个返回为词典序。若数据规模大且查询频繁，可以维护每节点缓存 Top K，但增删后的失效和排序口径会增加写成本。
用 set 保存参考词典，随机 add/search/delete/autocomplete 操作逐步对照；特别测共享前缀、删短词留长词、重复 add 和空词。

手动走一遍

add('pin')、add('pins')、add('pink') 后，search('pi') 为 false，autocomplete('pin',3) 为 ['pin','pink','pins']。delete('pin') 后仍能找到 'pink' 和 'pins'，因为共享前缀节点未被误删。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Trie training variant: exact search, deletion, and prefix suggestions."""


class TrieNode:
    def __init__(self):
        self.children = {}
        self.terminal = False


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

    def add(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.children.setdefault(char, TrieNode())
        node.terminal = True

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.terminal

    def delete(self, word: str) -> bool:
        node = self.root
        path = []
        for char in word:
            if char not in node.children:
                return False
            path.append((node, char))
            node = node.children[char]
        if not node.terminal:
            return False
        node.terminal = False
        for parent, char in reversed(path):
            child = parent.children[char]
            if child.terminal or child.children:
                break
            del parent.children[char]
        return True

    def autocomplete(self, prefix: str, k: int) -> list[str]:
        if k < 0:
            raise ValueError("k must be nonnegative")
        node = self._walk(prefix)
        if node is None or k == 0:
            return []
        result = []
        stack = [(node, prefix)]
        while stack and len(result) < k:
            current, word = stack.pop()
            if current.terminal:
                result.append(word)
            for char in sorted(current.children, reverse=True):
                stack.append((current.children[char], word + char))
        return result

    def _walk(self, text: str):
        node = self.root
        for char in text:
            node = node.children.get(char)
            if node is None:
                return None
        return node

复杂度

词长 L：add/search/delete O(L) 期望时间；autocomplete 先 O(|prefix|)，再需访问所返回词的路径及为确定词典序而遍历的节点，最坏 O(该前缀子树节点数×平均分支排序成本)，输出字符构造另有长度代价。总空间与存储的不同前缀节点数成正比。

易错点与追问

容易失分的边界

把 children 写成 class variable，所有 TrieNode 共享同一张表。
删除短词时把仍支撑长词的整条路径删掉。
search 只检查前缀可达，不检查 terminal。
宣称所有 autocomplete 查询 O(k)，忽略前缀定位、枚举与排序。
把外链的完整 add/search/delete 题面假定已知。

继续深挖

按词频和个性化热度排序时，如何维护每节点 Top K？
批量词典更新后如何原子发布给查询服务？
若只允许前缀建议而不存空字符串，root 的 terminal 应怎样处理？
多语言输入、大小写和 Unicode 规范化在索引前怎样统一？