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

题目描述#

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

实现词典类 WordDictionary：

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

思路#

嘿嘿，偷偷带你看一眼这题的小秘密～

嘿嘿，存储部分和 208. 实现 Trie 一毛一样——一棵前缀树，每个节点 26 个子指针 + 一个 isEnd 小旗子，搞定搞定～

真正的新朋友，是 search 里那个调皮的 .：它能假装成任何一个字母。遇到普通字母还好说，顺着一条路下探就行；可一旦撞上 .，就得分叉去敲 26 个子节点的门，只要有一扇开了、后面还能接得上，就算匹配成功～这种"走一步歧义、走一步剪枝"的姿势嘛——交给 DFS 递归 最舒服啦。

咱把 dfs(node, word) 的三条边界拎出来看看：

node == nil：这条路走不下去了，果断返回 false。
len(word) == 0：字符吃完啦，但别高兴得太早——必须当前节点真的是某个单词的结尾（isEnd == true）才算数。
否则看 word[0]：
- 普通字母 → 只递归对应子节点，规规矩矩。
- . → 遍历 26 个子节点，任一命中就举手喊"有啦！"，全军覆没才 false。

思维边界#

word 可能全是 .，这时候 DFS 每层都分 26 叉，最坏复杂度 O(26^L) 听着就头大。但放心啦，字典树节点稀疏得很，一碰到 nil 立刻剪枝——所有跑得飞快的算法，背后都站着一个"大多数路其实走不通"的好朋友。
千万别漏掉 len(word) == 0 时判 isEnd 这一脚！漏了就变成"前缀能走通也算命中"，悄咪咪把题目换成了 startsWith，上当啦～
切片 word[1:] 在 Go 里是 O(1) 视图、不会复制字符串，放心用，本姑娘拍胸脯保证！

边界拆明白啦，剩下的交给键盘——冲鸭！

代码#

type WordDictionary struct {
    root *Node
}

type Node struct {
    child [26]*Node
    isEnd bool
}

func Constructor() WordDictionary {
    return WordDictionary{
        root: &Node{},
    }
}

func (this *WordDictionary) AddWord(word string) {
    cur := this.root
    for _, v := range word {
        index := v - 'a'
        if cur.child[index] == nil {
            cur.child[index] = &Node{}
        }
        cur = cur.child[index]
    }
    cur.isEnd = true
}

func (this *WordDictionary) Search(word string) bool {
    // 使用深度优先搜索DFS
    return dfs(this.root, word)
}

func dfs(node *Node, word string) bool {
    if node == nil {
        return false
    }
    if len(word) == 0 {
        return node.isEnd
    }
    cur := word[0]
    if cur != '.' {
        return dfs(node.child[cur-'a'], word[1:])
    }
    // 当前说明字符为通配符 .
    for _, child := range node.child {
        if dfs(child, word[1:]) {
            return true
        }
    }
    // 这里说明没找到对应结果
    return false
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddWord(word);
 * param_2 := obj.Search(word);
 */