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

两句话记住：建树时「最后一个字母的节点」标绿当词尾；查的时候普通字母照着走、遇到 . 就把所有孩子都试一遍。

addWord("bad")：从根出发，按字母 b→a→d 一路建出三个节点。最后一个字母 d 所在的节点打上绿色「词尾」标记，表示「bad 是一个完整单词」。

addWord("dad")：根下面没有 d 这个孩子，于是新建一条 d→a→d 的路径。末位 d 节点再标绿当词尾，表示「dad 也是一个完整单词」。

addWord("mad")：同样新建一条 m→a→d 路径，末位标绿。至此树里存了 bad / dad / mad 三个单词，根下面有 b、d、m 三个分叉。

search("pad")：先看第一个字母 p。从根出发要找一个叫 p 的孩子——可是根下面只有 b、d、m，没有 p。第一步就走不通了。

根的孩子里压根没有 p，路直接断了。还没轮到后面的 a、d 就已经失败，search("pad") 返回 false。

search(".ad")：第一个字符是 . ，不知道走哪个字母，就把根的所有孩子都当候选——b、d、m 全部要试一遍（高亮的三个）。我们先从 b 这条岔路试。

进入 b 分支后，第二个字符是普通字母 a：看 b 的孩子里有没有 a——有，走到 a 节点。万能字符那一步只在第一层分叉，后面照常走。

第三个字符 d：a 的孩子里有 d，走到末位的 d 节点。字符串 .ad 三个字符全部走完了，停在这个节点上。

停下的这个节点正好是绿色词尾——说明 b+a+d=bad 是一个真实存在的完整单词，.ad 成功匹配到它。只要有一条岔路能走到词尾就够了，search(".ad") 返回 true。

search("b..")：第一个字符是普通字母 b，照常走——根的孩子里有 b，走到 b 节点。注意这次开头不是 . ，所以只走 b 这一条，不用试 d、m。

第二个字符是 . ：把 b 的所有孩子都试一遍。b 只有一个孩子 a，于是走到 a 节点。

第三个字符又是 . ：把 a 的所有孩子都试一遍。a 只有一个孩子 d，走到末位 d 节点。b.. 三个字符走完了。

走完三个字符停在绿色词尾节点上——b.. 匹配到了 bad。search("b..") 返回 true。两个 . 各自把当前节点的孩子试了一遍，凑出了一条通往词尾的路。

再看个反例 search("ba")：照着 b→a 走到 a 节点就停（两个字符走完）。但 a 节点不是绿色——它只是 bad 路上的中间点，不是词尾。

停下的 a 节点没有词尾标记，说明 ba 只是某个单词的前缀、不是完整单词。所以 search("ba") 返回 false——这就是为什么「走到末位还要再检查是不是词尾」。

search("..d")：第一个字符就是 . ，要把根的三个孩子 b、d、m 全部当候选。下面跟着其中一条（比如 d 这条）走，其它两条同理。

沿 d 这条岔路往下：第二个字符又是 . ，把 d 的孩子全试一遍。d 只有一个孩子 a，走到 a 节点。

第三个字符是普通字母 d：a 的孩子里有 d，走到末位。三个字符走完，停在 d→a→d 这条路的尾节点。

末位是绿色词尾——dad 是完整单词，..d 匹配成功。其实 b→a→d、m→a→d 三条都能走到词尾，任意一条成立就返回 true，search("..d") = true。

再看 search(".at")：第一个 . 试到 b 这条，第二个普通字母 a 走到 a 节点。前两步都对得上，停在 a 节点准备走第三个字符 t。

第三个字符是普通字母 t：可是 a 的孩子只有 d、没有 t，这条路断了。换 d、m 两条岔路第三步也都只有 d 没有 t。三条全断，search(".at") 返回 false。

三个高频追问：为什么用 Trie、为什么 . 要递归、全 . 的极端情况。