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

这道题到底在问什么

输入

addWord("bad"), addWord("dad"), addWord("mad")

输出

三个单词存入

输入

search("pad")

输出

false

输入

search(".ad")

输出

true（.ad 能匹配 bad/dad/mad）

输入

search("b..")

输出

true（b.. 能匹配 bad）

最优解：一步一步想明白

1. 3两句话记住：建树时「最后一个字母的节点」标绿当词尾；查的时候普通字母照着走、遇到 . 就把所有孩子都试一遍。
2. 4addWord("bad")：从根出发，按字母 b→a→d 一路建出三个节点。最后一个字母 d 所在的节点打上绿色「词尾」标记，表示「bad 是一个完整单词」。
3. 5addWord("dad")：根下面没有 d 这个孩子，于是新建一条 d→a→d 的路径。末位 d 节点再标绿当词尾，表示「dad 也是一个完整单词」。
4. 6addWord("mad")：同样新建一条 m→a→d 路径，末位标绿。至此树里存了 bad / dad / mad 三个单词，根下面有 b、d、m 三个分叉。
5. 7search("pad")：先看第一个字母 p。从根出发要找一个叫 p 的孩子——可是根下面只有 b、d、m，没有 p。第一步就走不通了。
6. 8根的孩子里压根没有 p，路直接断了。还没轮到后面的 a、d 就已经失败，search("pad") 返回 false。
7. 9search(".ad")：第一个字符是 . ，不知道走哪个字母，就把根的所有孩子都当候选——b、d、m 全部要试一遍（高亮的三个）。我们先从 b 这条岔路试。
8. 10进入 b 分支后，第二个字符是普通字母 a：看 b 的孩子里有没有 a——有，走到 a 节点。万能字符那一步只在第一层分叉，后面照常走。
9. 11第三个字符 d：a 的孩子里有 d，走到末位的 d 节点。字符串 .ad 三个字符全部走完了，停在这个节点上。
10. 12停下的这个节点正好是绿色词尾——说明 b+a+d=bad 是一个真实存在的完整单词，.ad 成功匹配到它。只要有一条岔路能走到词尾就够了，search(".ad") 返回 true。
11. 13search("b..")：第一个字符是普通字母 b，照常走——根的孩子里有 b，走到 b 节点。注意这次开头不是 . ，所以只走 b 这一条，不用试 d、m。
12. 14第二个字符是 . ：把 b 的所有孩子都试一遍。b 只有一个孩子 a，于是走到 a 节点。
13. 15第三个字符又是 . ：把 a 的所有孩子都试一遍。a 只有一个孩子 d，走到末位 d 节点。b.. 三个字符走完了。
14. 16走完三个字符停在绿色词尾节点上——b.. 匹配到了 bad。search("b..") 返回 true。两个 . 各自把当前节点的孩子试了一遍，凑出了一条通往词尾的路。
15. 17再看个反例 search("ba")：照着 b→a 走到 a 节点就停（两个字符走完）。但 a 节点不是绿色——它只是 bad 路上的中间点，不是词尾。
16. 18停下的 a 节点没有词尾标记，说明 ba 只是某个单词的前缀、不是完整单词。所以 search("ba") 返回 false——这就是为什么「走到末位还要再检查是不是词尾」。
17. 19search("..d")：第一个字符就是 . ，要把根的三个孩子 b、d、m 全部当候选。下面跟着其中一条（比如 d 这条）走，其它两条同理。
18. 20沿 d 这条岔路往下：第二个字符又是 . ，把 d 的孩子全试一遍。d 只有一个孩子 a，走到 a 节点。
19. 21第三个字符是普通字母 d：a 的孩子里有 d，走到末位。三个字符走完，停在 d→a→d 这条路的尾节点。
20. 22末位是绿色词尾——dad 是完整单词，..d 匹配成功。其实 b→a→d、m→a→d 三条都能走到词尾，任意一条成立就返回 true，search("..d") = true。
21. 23再看 search(".at")：第一个 . 试到 b 这条，第二个普通字母 a 走到 a 节点。前两步都对得上，停在 a 节点准备走第三个字符 t。
22. 24第三个字符是普通字母 t：可是 a 的孩子只有 d、没有 t，这条路断了。换 d、m 两条岔路第三步也都只有 d 没有 t。三条全断，search(".at") 返回 false。

⚠️ 容易写错的地方

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

class WordDictionary:
    def __init__(self):
        self.kids = {}          # 26 个孩子
        self.end = False        # 是否词尾
    def addWord(self, word):
        node = self
        for c in word:          # 顺着字母往下建
            node = node.kids.setdefault(c, WordDictionary())
        node.end = True         # 末位标词尾
    def search(self, word):
        def dfs(node, i):
            if i == len(word):  # 字符走完
                return node.end # 看是不是词尾
            c = word[i]
            if c == '.':        # 万能字符
                for nxt in node.kids.values():
                    if dfs(nxt, i + 1): return True
                return False
            if c not in node.kids: return False
            return dfs(node.kids[c], i + 1)
        return dfs(self, 0)

struct WordDictionary {
    WordDictionary* kids[26] = {};
    bool end = false;
    void addWord(string w) {
        auto* n = this;
        for (char c : w) {
            int k = c - 'a';
            if (!n->kids[k]) n->kids[k] = new WordDictionary();
            n = n->kids[k];
        }
        n->end = true;
    }
    bool dfs(WordDictionary* n, string& w, int i) {
        if (i == w.size()) return n->end;
        if (w[i] == '.') {
            for (auto* nx : n->kids)
                if (nx && dfs(nx, w, i + 1)) return true;
            return false;
        }
        auto* nx = n->kids[w[i] - 'a'];
        return nx && dfs(nx, w, i + 1);
    }
    bool search(string w) { return dfs(this, w, 0); }
};

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

复杂度

面试官可能追问