0211. Design Add and Search Words Data Structure ================================================ 题目信息 -------- :题号: 0211. 添加与搜索单词——数据结构设计 :难度: Medium :主题: Trie、通配符搜索、递归搜索、对象状态 :原题: `LeetCode 0211 `_ :重点: 点号匹配一个字符、完整单词与前缀、共享前缀、跨调用状态 题目重述 -------- 设计一个可以连续使用的 ``WordDictionary``。``addWord(word)`` 把一个只含小写字母的单词加入字典; ``search(pattern)`` 判断字典中是否存在某个此前加入的完整单词,能够与模式逐位匹配。模式中的普通字母只能匹配同一个字母, 点号 ``.`` 可以匹配任意一个小写字母,但恰好消耗一个字符,不能代表空串或多个字符。 搜索成功不仅要求字符路径匹配,还要求模式结束的位置正好是某个已加入单词的终点。一个单词的前缀路径存在,不能说明这个前缀本身 已经被加入。字典必须跨越多次 ``addWord``、``search`` 调用保存状态;单词和模式长度最多为 25,模式最多含两个点号,所有操作总数最多为 ``10^4``。 自建示例 -------- 加入 ``"bad"``、``"dad"``、``"mad"`` 后:``search(".ad")`` 返回 ``true``,因为点号可以选择三条首字母分支中的任意一条; ``search("b..")`` 返回 ``true``,两个点号各消费一个字符;``search(".ae")`` 返回 ``false``,所有首字母分支都会在最后的 ``e`` 处失败, 因为这是“存在一条成功分支”的搜索,不是只检查一个固定单词。 加入 ``"rain"`` 后,``search("rai")`` 返回 ``false``,因为 ``rai`` 只是更长单词的前缀;``search("ra.n")`` 返回 ``true``, 点号匹配 ``i`` 后到达 ``rain`` 的终点。 若依次加入 ``"apple"``、``"app"``,查询 ``"app"`` 只有在第二次加入后才返回 ``true``。同一条路径既可以是完整单词终点, 也可以继续通向更长单词,终止状态不能从“有没有孩子”推断。 C++ 实现 -------- .. code-block:: cpp #include #include #include class WordDictionary { private: struct Node { std::array, 26> children{}; bool terminal = false; }; Node root_; bool matches(const Node* node, const std::string& pattern, std::size_t position) const { if (position == pattern.size()) return node->terminal; const char character = pattern[position]; if (character != '.') { const int index = character - 'a'; const Node* child = node->children[index].get(); return child != nullptr && matches(child, pattern, position + 1); } for (const std::unique_ptr& child : node->children) { if (child != nullptr && matches(child.get(), pattern, position + 1)) { return true; } } return false; } public: WordDictionary() = default; void addWord(const std::string& word) { Node* node = &root_; for (char character : word) { const int index = character - 'a'; if (node->children[index] == nullptr) { node->children[index] = std::make_unique(); } node = node->children[index].get(); } node->terminal = true; } bool search(const std::string& pattern) const { return matches(&root_, pattern, 0); } }; 题解 ---- 原始搜索空间 ~~~~~~~~~~~~ 最直接的结构是保存所有单词。查询时逐个检查长度相同的候选,普通字符比较是否相等,``.`` 直接跳过比较;检查完一个完整单词才算 命中。它覆盖了字典中的每个可能答案,因此不会漏解,但一次查询最坏要比较 ``W`` 个单词的 ``L`` 个字符,时间为 ``O(WL)``。 真正重复的不是某次字符比较,而是共享前缀被反复读取。例如 ``bad``、``dad``、``mad`` 都让 ``.ad`` 重新检查相同的后缀。 若预先为每个单词枚举所有点号替换,又会把 ``26`` 分支的成本提前支付给每次插入,查询模式的表达也变得不直接。 共享前缀与终点标记 ~~~~~~~~~~~~~~~~~~ Trie 节点表示“已经匹配的前缀”,边表示下一个小写字母。插入时已有边直接复用,只有缺边才创建节点,所以公共前缀只保存一次。 但路径存在仍不等于完整单词存在:``apple`` 会建立 ``app`` 节点,却不能让 ``search("app")`` 成功;``terminal`` 专门记录路径本身 是否在某次 ``addWord`` 中结束。之后再加入 ``app`` 只需设置同一个节点的标志。 搜索状态与转移 ~~~~~~~~~~~~~~ ``matches(node, position)`` 表示:Trie 根到 ``node`` 的路径已经匹配模式的 ``pattern[0..position)``,现在判断剩余模式能否抵达终点。 状态始终满足“节点路径”和“已消费字符数”描述同一条候选路径: * 模式结束时只检查 ``node->terminal``,不再向下走; * 当前字符是字母时只有一条可能边,缺边即可剪枝; * 当前字符是 ``.`` 时枚举当前节点真实存在的非空子边,每条分支恰好消费一个字符; * 点号分支是“存在一条成功路径”,某一分支成功就短路,全部失败才返回假。 这解释了两个容易混淆的结果:``rai`` 到达有 ``n`` 子边的节点却因 ``terminal=false`` 失败;``ra.n`` 的点号只匹配 ``i``,不会跳过 字符。查询只读 Trie,跨调用的不变量仍由 ``addWord`` 保持。 状态走读 ~~~~~~~~ 加入 ``bad``、``dad``、``mad`` 后查询 ``.ad``: .. list-table:: :header-rows: 1 * - 状态 - 当前字符 - 转移与结论 * - ``(root,0)`` - ``.`` - 只枚举实际存在的 ``b``、``d``、``m`` 三条边 * - ``(b,1)`` - ``a`` - 沿唯一 ``b->a`` 边前进 * - ``(ba,2)`` - ``d`` - 到达 ``bad`` 节点 * - ``(bad,3)`` - 模式耗尽 - ``terminal=true``,返回真并停止其他分支 若查询 ``.ae``,三条根边都能消费首个点号,但 ``ba``、``da``、``ma`` 都没有 ``e`` 边,于是三个分支分别失败。若查询 ``app``, ``apple`` 只有路径没有终止标记;加入 ``app`` 后,同一节点的 ``terminal`` 才改变,说明结构状态和单词状态必须分开保存。 方案选择与复杂度 ~~~~~~~~~~~~~~~~~~ 字符串列表保留了完整候选,最坏 ``O(WL)``;Trie 插入一个长度为 ``L`` 的单词为 ``O(L)``。无点号查询每层只有一条边,时间为 ``O(L)``; 含点号查询按实际访问的 ``(节点,模式位置)`` 状态计费,点号多且分支多时仍可能指数增长。Trie 的收益是共享已经确认的前缀,而不是 消除题目本身允许的通配符选择。代码采用固定 26 个子链接,实际节点数为 ``N`` 时空间为 ``O(N)``,递归栈最多 ``O(L)``。 代码走读 -------- ``root_`` 是跨调用保存字典的根节点。``addWord`` 沿字符路径向下走:已有链接被复用,空链接才分配新节点;循环结束后才设置 ``terminal``,所以 ``app`` 可以先作为 ``apple`` 的中间节点,之后再独立成为完整单词。``unique_ptr`` 让根节点拥有整棵 Trie, 对象销毁时子节点会自动释放,不需要另写平行的释放遍历。 ``matches`` 的两个分支对应题目的两种匹配规则。普通字母先按下标取唯一子节点,缺失时立即剪枝;点号遍历当前节点已有的子节点, 任一递归成功就短路返回。递归参数中的 ``position`` 每次恰好加一,保证点号只匹配一个字符;到达模式末尾后才检查 ``terminal``, 不会把前缀误报为完整单词。``search`` 声明为只读,递归使用 ``const Node*``,从类型上表达查询不改变跨调用状态。 复杂度与边界 ~~~~~~~~~~~~ 设单词长度上限为 ``L``,Trie 实际节点数为 ``N``。``addWord`` 每个字符只走一次,时间为 ``O(L)``,固定 26 个子链接使额外空间为 ``O(26N)``,常数字母表下记为 ``O(N)``。无点号查询每层只有一条路径,时间为 ``O(L)``;含点号查询按实际访问的 ``(Trie 节点, 模式位置)`` 状态数 ``Q`` 计为 ``O(Q)``,最坏才接近所有与长度相容的分支。 递归栈深度最多为 ``O(L)``。空字典会在第一条缺失边返回假;长度为 1 的模式在消费一个字符后立即检查终点;重复加入同一单词只会 再次设置同一个终止标记,不改变搜索结果。输入模式中的点号不会与 Trie 的真实字母边混淆,因为它只在查询分支中解释,插入操作只接受字母。