添加与搜索单词 - 数据结构设计 图解题解

这道题到底在问什么

存入

addWord("bad")、addWord("dad")、addWord("mad")

查询

search(".ad") → true；search("b..") → true；search(".at") → false

最优解：一步一步想明白

1. 3思路一句话：单词建成前缀树；查询时普通字母顺着唯一一条边往下走，碰到点号就对当前节点的每个孩子都递归试一遍。下面 5 步动画把这两种走法都画出来。
2. 4bad / dad / mad 共享后两位 a、d，末节点标词尾addWord 和 LC208 前缀树一模一样：把单词逐字符建成一条从根往下的路径。这里已存入 bad、dad、mad——三个词首字母不同，但都共用后两位 a、d。绿色的三个 d 是词尾标记，代表「走到这里是一个完整单词」。
3. 5b → a → d 一路走通，终点是词尾 → true先看最简单的：查 bad 没有点号。字母是确定的，所以每一步只有唯一一条边可走：从根挑 b、再挑 a、再挑 d。三个 d 都是词尾，但这次只走到了 db 这一个，所以只有它亮绿——绿色在查询帧里表示「本次走通并命中的终点」，另外两个词尾没被走到就不高亮，词尾属性它们一直都有。终点带词尾，于是返回 true。这就是普通前缀树查询。
4. 6到点号这一位，不知该走 b 还是 d 还是 m → 全都得试现在查 ".ad"。第一位是点号，它能当任意字母。问题就来了：站在根上，到底该走 b、d 还是 m？答案是——三条都得试。蓝色高亮的就是「待尝试的所有孩子」。这一位分叉成三条支路，正是通配查询比普通查询难的根源。
5. 7先试 b 分支：b → a → d 命中词尾 → 立即返回 trueDFS 从点号的三条分支里挑第一条 b 试：b → a → d，词尾命中！亮绿的 db 表示「本次走通并命中的终点」，dd、dm 这次没被走到所以不亮绿——它们的词尾属性还在，只是这条查询没碰到。只要任意一条路走通就够了，立刻返回 true，剩下的 d、m 两条分支（还留着蓝色）根本不用再走。bad、dad、mad 里只要有一个能配上 .ad，结果就是 true。
6. 8b 先走唯一孩子到 ab，再两个点号在这条线上各只有一个孩子可分叉 → 走到底命中 → true再看一个混合情形：查 "b.."——前缀是确定字母、后面跟两个点号。第一位 b 是确定字母，只走唯一一条边到 a（ab）；接着第二位是点号，但站在 ab 上这条线只有一个孩子 d，分叉口里其实只有一条可走；第三位又是点号，同理走到底的 db 带词尾——命中，返回 true。这一帧把两种机制接在一条查询里：确定字母「走唯一孩子」紧接着点号「试所有孩子」，正是本题最典型的走法。
7. 9b/d/m 三条分支，第三个字母都缺 t → 全部失败再看一个返回 false 的：查 ".at"。点号同样把 b、d、m 三条分支都试一遍，每条往下第二个字母 a 都对得上，可第三个字母要 t——而这一层树里只有 d，没有 t。三条分支全部走到底却都不匹配，没有任何一个词尾被命中，所以这帧没有绿色（绿色只在「本次成功命中词尾」时才亮）。DFS 退回根、再无可试，最终返回 false。
8. 10b 分支刚试完失败 → 灰掉回退 → 现在轮到 d 分支(蓝→正在试)，m 还排队把上一帧慢放，看清 DFS 的核心节律。b 分支刚刚走到底发现第三位没有 t，失败——它和它下面的 a 不再高亮（灰掉），表示「这条试过了、回退」。回退后轮到第二条 d 分支：现在它亮成蓝色正在试（r → d1 → ad），往下第三位同样卡在没有 t，又会失败回退；最后还排队等着的 m 分支也是一样的结局。这种「试一条 → 不行 → 灰掉回退 → 换下一条」就是递归 DFS 天生擅长的回溯，对应代码里 for 循环逐个孩子 dfs、谁返回 true 就停。
9. 13一句话本质：前缀树负责存，DFS 负责查；普通字母只有一条路、点号是个分叉口。把这句记住，这道题就拿下了。
10. 15b → a 路径明明在树里，但 a 这个节点没有词尾标记(非绿色) → false把雷区一在这棵现成的树上真跑一遍：存过 bad，现在查 ba。b → a 这条路确实走得通（r → b → ab 都点亮了），ba 在树里是一段真实存在的前缀。但关键看终点 ab 这个 a 节点——它只是 bad 半路上的字母，词尾标记长在再往下的 db 上（图里那个绿色的 d 才是 bad 的真正词尾），ab 自己没有词尾标记（它没亮绿，只是蓝色的「到达点」）。所以 dfs 在末尾检查 node.end 时得到 false：路径在 ≠ 存过这个词。这正是「忘查词尾」会翻车的根因——画出来一眼就懂。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class WordDictionary:
    def __init__(self):
        self.root = {}
    def addWord(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['#'] = True   # 词尾标记
    def search(self, word):
        def dfs(i, node):
            if i == len(word):
                return '#' in node
            ch = word[i]
            if ch == '.':
                for key, nxt in node.items():
                    if key != '#' and dfs(i + 1, nxt):
                        return True
                return False
            if ch not in node:
                return False
            return dfs(i + 1, node[ch])
        return dfs(0, self.root)

class WordDictionary {
    struct Node { Node* ch[26] = {}; bool end = false; };
    Node* root = new Node();
    bool dfs(const string& w, int i, Node* node) {
        if (i == (int)w.size()) return node->end;
        if (w[i] == '.') {
            for (int k = 0; k < 26; k++)
                if (node->ch[k] && dfs(w, i+1, node->ch[k])) return true;
            return false;
        }
        Node* nxt = node->ch[w[i]-'a'];
        return nxt && dfs(w, i+1, nxt);
    }
public:
    void addWord(string word) {
        Node* node = root;
        for (char c : word) {
            int k = c - 'a';
            if (!node->ch[k]) node->ch[k] = new Node();
            node = node->ch[k];
        }
        node->end = true;
    }
    bool search(string word) { return dfs(word, 0, root); }
};

class WordDictionary {
    class Node { Node[] ch = new Node[26]; boolean end = false; }
    Node root = new Node();
    public void addWord(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            int k = c - 'a';
            if (node.ch[k] == null) node.ch[k] = new Node();
            node = node.ch[k];
        }
        node.end = true;
    }
    public boolean search(String word) { return dfs(word, 0, root); }
    boolean dfs(String w, int i, Node node) {
        if (i == w.length()) return node.end;
        char c = w.charAt(i);
        if (c == '.') {
            for (int k = 0; k < 26; k++)
                if (node.ch[k] != null && dfs(w, i+1, node.ch[k])) return true;
            return false;
        }
        Node nxt = node.ch[c-'a'];
        return nxt != null && dfs(w, i+1, nxt);
    }
}

# 通配前缀树查询骨架：把 '确定字母走唯一孩子 / 通配试所有孩子' 背下来
def dfs(i, node):
    if i == len(word):          # 1) 走到末尾
        return ____             #    → 看词尾标记，别直接 True
    ch = word[i]
    if ch == WILDCARD:          # 2) 通配位：分叉
        for nxt in ____:        #    遍历当前节点所有孩子
            if dfs(i + 1, nxt): #    任一成功即成功
                return True
        return False
    if ch not in node:          # 3) 确定字母：唯一孩子
        return False            #    没这条边直接失败
    return dfs(i + 1, node[ch])

// 三步骨架：末尾看词尾 / 通配遍历孩子 / 确定字母走唯一孩子
bool dfs(int i, Node* node) {
    if (i == n) return ____;        // 1) 末尾：返回 node->end
    if (w[i] == WILDCARD) {         // 2) 通配位：分叉
        for (auto nxt : children)   //    遍历所有孩子
            if (nxt && dfs(i+1, nxt)) return true;
        return false;
    }
    Node* nxt = ____;               // 3) 确定字母：唯一孩子
    return nxt && dfs(i+1, nxt);
}

// 背这三句：末尾看 end / 通配 for 遍孩子 / 确定字母走唯一孩子
boolean dfs(int i, Node node) {
    if (i == n) return ____;        // 1) 末尾：返回 node.end
    if (w[i] == WILDCARD) {         // 2) 通配位：分叉
        for (Node nxt : children)   //    遍历所有孩子
            if (nxt != null && dfs(i+1, nxt)) return true;
        return false;
    }
    Node nxt = ____;                // 3) 确定字母：唯一孩子
    return nxt != null && dfs(i+1, nxt);
}

复杂度

面试官可能追问