LeetCode 211. 添加与搜索单词 - 数据结构设计

约 6 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 面试经典 150 题 字节
标签
字符串 深度优先搜索 设计 字典树

题目描述

✅ 211. 添加与搜索单词 - 数据结构设计

image-20260928230939847

image-20260928230939848

题意分析

支持添加单词和搜索模式，点恰好匹配任意一个字母，搜索必须覆盖整个已存单词。

解法：Trie + DFS

核心思路

[!blue]

用 Trie 让不同单词共享相同的前缀路径。根节点表示空前缀，每向下走一条字母边，就多匹配一个字符；每个节点用 26 个孩子位置对应小写字母。添加单词时，沿已有路径前进，缺少节点就创建，只在整个单词末端设置 isEnd。

搜索状态 dfs(word, pos, node) 表示：模式的 [0, pos) 已经匹配到 node，接下来匹配 pos 处字符。普通字母只能沿对应的一个孩子继续，孩子不存在就失败；点号可以匹配任意一个字母，所以尝试当前节点的所有非空孩子，每次都让 pos 加一。

点号的某个分支成功即可返回 true，某个分支失败则仍要尝试其他孩子，全部失败后才返回 false。这会覆盖点号的所有合法匹配，不需要把点号展开成实际字符串。

当 pos 到达模式长度时，还要检查 node.isEnd：路径存在只说明它是某个单词的前缀，只有终止标记才说明整个模式匹配了一个已添加的完整单词。每次递归都消耗恰好一个字符，所以点号也只能匹配一个字母，搜索最多递归到模式长度。

解题步骤

  • 添加时逐字符建立路径，末端标记完整词。
  • 搜索按位置与节点递归，空节点失败。
  • 模式结束返回终止标记。
  • 普通项走唯一边，点尝试全部孩子后再决定失败。

代码实现

class WordDictionary {
    private final TrieNode root = new TrieNode();

    public WordDictionary() {}

    public void addWord(String word) {
        TrieNode node = root;

        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';

            if (node.next[idx] == null) {
                node.next[idx] = new TrieNode();
            }

            node = node.next[idx];
        }

        // 只在整个单词的末端标记，不将普通前缀当作单词
        node.isEnd = true;
    }

    public boolean search(String word) {
        return dfs(word, 0, root);
    }

    private boolean dfs(String word, int pos, TrieNode node) {
        if (node == null) {
            return false;
        }

        if (pos == word.length()) {
            // 模式耗尽还要确认落在完整单词末端
            return node.isEnd;
        }

        char c = word.charAt(pos);

        if (c == '.') {
            // 通配分支只有成功才能提前结束，失败后仍要试其他孩子
            for (TrieNode child : node.next) {
                if (child != null && dfs(word, pos + 1, child)) {
                    return true;
                }
            }

            return false;
        }

        return dfs(word, pos + 1, node.next[c - 'a']);
    }

    private static class TrieNode {
        TrieNode[] next = new TrieNode[26];
        boolean isEnd;
    }
}

type WordDictionary struct {
    root *TrieNode
}

type TrieNode struct {
    next  [26]*TrieNode
    isEnd bool
}

func Constructor() WordDictionary {
    return WordDictionary{root: new(TrieNode)}
}

func (w *WordDictionary) AddWord(word string) {
    node := w.root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if node.next[idx] == nil {
            node.next[idx] = &TrieNode{}
        }
        node = node.next[idx]
    }
    // 只在整个单词的末端标记，不将普通前缀当作单词
    node.isEnd = true
}

func (w *WordDictionary) Search(word string) bool {
    var dfs func(int, *TrieNode) bool
    dfs = func(pos int, node *TrieNode) bool {
        if node == nil {
            return false
        }
        if pos == len(word) {
            // 模式耗尽还要确认落在完整单词末端
            return node.isEnd
        }

        c := word[pos]
        if c == '.' {
            // 通配分支只有成功才能提前结束，失败后仍要试其他孩子
            for i := 0; i < 26; i++ {
                if node.next[i] != nil && dfs(pos+1, node.next[i]) {
                    return true
                }
            }
            return false
        }

        return dfs(pos+1, node.next[c-'a'])
    }

    return dfs(0, w.root)
}

复杂度分析

设当前单词或查询模式长度为 L，累计添加单词的字符总数为 N。

  • 时间复杂度：添加为 $O(L)$；查询中每个点最多产生 26 个分支，含 k 个点时上界为 $O(26^kL)$，实际只访问已有节点。没有点时沿唯一路径查找，为 $O(L)$。
  • 空间复杂度：$O(N+1)$ 保存 Trie，N 为累计单词字符数；另有 $O(L)$ 查询递归栈，字母表大小固定。

关键点总结

[!green]

  • 终止标记使完整匹配不同于前缀匹配。
  • 通配分支只有成功才能提前返回。

易错点总结

[!yellow]

  • 模式结束无条件成功，会把尚未作为完整单词添加的前缀误判为存在。
  • 首个孩子失败就返回，会漏掉后面可匹配分支。
  • 添加时把中途节点也标记为完整词，会伪造前缀单词。

相似题目

题目 难度 关联与区别
208. 实现 Trie (前缀树) 中等 基础Trie支持精确与前缀查询，本题增加点号通配符，需在多个孩子之间搜索。
676. 实现一个魔法字典 中等 同样在Trie中允许匹配偏差，原题必须恰好替换一个字符，本题偏差位置由点号直接给出。
212. 单词搜索 II 困难 用字典树共享字符串前缀；本题通配符查询时分支搜索，该题把字典树与网格回溯结合。
648. 单词替换 中等 用字典树共享字符串前缀；本题通配符查询时分支搜索，该题沿词前缀找到最短词根。
677. 键值映射 中等 用字典树共享字符串前缀；本题通配符查询时分支搜索，该题在前缀节点累计键值总和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/87049048
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！