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

题目描述：

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

实现词典类 WordDictionary ：

• WordDictionary() 初始化词典对象
• void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
• bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。 word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。

示例：

输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]

解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // 返回 False
wordDictionary.search("bad"); // 返回 True
wordDictionary.search(".ad"); // 返回 True
wordDictionary.search("b.."); // 返回 True

提示：

• 1 <= word.length <= 25
• addWord 中的 word 由小写英文字母组成
• search 中的 word 由 ’.’ 或小写英文字母组成
• 最多调用 104 次 addWord 和 search

---

解题分析及思路：

方法：深度优先搜索 + 字典树

思路：

本题的核心是高效处理精确添加和模糊搜索需求，适合采用 Trie（字典树） 数据结构：

• Trie的优势：Trie通过字符分层存储，添加单词时按字符顺序构建树结构，搜索时可按字符逐层匹配，天然适配字符串的前缀/全量匹配场景。
• 模糊搜索处理：对于通配符 '.'，需遍历当前节点的所有可能子节点（26个小写字母），通过递归尝试所有路径，判断是否存在匹配的单词。

Trie节点结构定义为 WordDictionary，包含两个核心字段：

• WordDictionaries [26]*WordDictionary：子节点数组，对应26个小写字母（索引 0-25 分别对应 a-z）。
• IsEnd bool：标记当前节点是否为某个单词的结尾。

步骤1：初始化Trie树（Constructor）

创建根节点，初始化子节点数组为空（默认值为 nil），IsEnd 默认为 false。

步骤2：添加单词（AddWord）

• 从根节点开始，按单词的字符顺序逐层构建Trie：
  1. 取当前字符对应的索引（word[0] - 'a'）。
  2. 若对应子节点不存在，则创建新节点并赋值给该索引。
  3. 递归处理剩余字符（word[1:]），直到单词长度为0。
  4. 当单词处理完毕，将当前节点的 IsEnd 标记为 true，表示此处是一个单词的结尾。

步骤3：搜索单词（Search）

• 从根节点开始，按搜索词的字符逐层匹配：
  1. 若搜索词长度为0，返回当前节点的 IsEnd（判断是否为单词结尾）。
  2. 若当前字符是 '.'：遍历所有非空的子节点，递归搜索剩余字符，若任一子节点路径匹配成功则返回 true。
  3. 若当前字符是小写字母：检查对应子节点是否存在，若存在则递归搜索剩余字符；否则返回 false。

// 定义Trie节点结构
type WordDictionary struct {
    WordDictionaries [26]*WordDictionary  // 子节点数组，对应a-z
    IsEnd            bool                 // 标记单词结尾
}

// 初始化Trie根节点
func Constructor() WordDictionary {
    return WordDictionary{
        WordDictionaries: [26]*WordDictionary{},  // 初始化子节点数组（默认nil）
    }
}

// 添加单词到Trie树
func (this *WordDictionary) AddWord(word string) {
    // 单词处理完毕，标记当前节点为单词结尾
    if len(word) == 0 {
        this.IsEnd = true
        return
    }
    // 计算当前字符对应的子节点索引（a-z对应0-25）
    now := word[0] - 'a'
    // 若子节点不存在，创建新节点
    if this.WordDictionaries[now] == nil {
        n := Constructor()  // 初始化新节点
        this.WordDictionaries[now] = &n
    }
    // 递归添加剩余字符
    this.WordDictionaries[now].AddWord(word[1:])
}

// 搜索单词（支持通配符'.'）
func (this *WordDictionary) Search(word string) bool {
    // 单词搜索完毕，判断当前节点是否为结尾
    if len(word) == 0 {
        return this.IsEnd
    }
    // 处理通配符'.'：遍历所有可能的子节点
    if word[0] == '.' {
        // 遍历26个小写字母对应的子节点
        for index := range this.WordDictionaries {
            // 若子节点存在，递归搜索剩余字符
            if v := this.WordDictionaries[index]; v != nil {
                if v.Search(word[1:]) {
                    return true  // 任一子节点匹配成功则返回true
                }
            }
        }
    } else {
        // 处理普通字符：计算索引并检查子节点
        now := word[0] - 'a'
        if v := this.WordDictionaries[now]; v != nil {
            // 子节点存在，递归搜索剩余字符
            return v.Search(word[1:])
        }
    }
    // 所有路径均不匹配
    return false
}

复杂度：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:0 ms,击败了100.00 的Go用户
• 内存消耗:2.4 MB,击败了99.83 的Go用户