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

思路一句话：单词建成前缀树；查询时普通字母顺着唯一一条边往下走，碰到点号就对当前节点的每个孩子都递归试一遍。下面 5 步动画把这两种走法都画出来。

addWord · 像前缀树一样建路径：addWord 和 LC208 前缀树一模一样：把单词逐字符建成一条从根往下的路径。这里已存入 bad、dad、mad——三个词首字母不同，但都共用后两位 a、d。绿色的三个 d 是词尾标记，代表「走到这里是一个完整单词」。

search("bad") · 没有点号，顺着唯一路径走：先看最简单的：查 bad 没有点号。字母是确定的，所以每一步只有唯一一条边可走：从根挑 b、再挑 a、再挑 d。三个 d 都是词尾，但这次只走到了 db 这一个，所以只有它亮绿——绿色在查询帧里表示「本次走通并命中的终点」，另外两个词尾没被走到就不高亮，词尾属性它们一直都有。终点带词尾，于是返回 true。这就是普通前缀树查询。

难点 · 点号「.」能匹配任意字母：现在查 ".ad"。第一位是点号，它能当任意字母。问题就来了：站在根上，到底该走 b、d 还是 m？答案是——三条都得试。蓝色高亮的就是「待尝试的所有孩子」。这一位分叉成三条支路，正是通配查询比普通查询难的根源。

search(".ad") · DFS 逐条分支试，命中即停：DFS 从点号的三条分支里挑第一条 b 试：b → a → d，词尾命中！亮绿的 db 表示「本次走通并命中的终点」，dd、dm 这次没被走到所以不亮绿——它们的词尾属性还在，只是这条查询没碰到。只要任意一条路走通就够了，立刻返回 true，剩下的 d、m 两条分支（还留着蓝色）根本不用再走。bad、dad、mad 里只要有一个能配上 .ad，结果就是 true。

search("b..") · 确定字母 + 连续点号的混合走法：再看一个混合情形：查 "b.."——前缀是确定字母、后面跟两个点号。第一位 b 是确定字母，只走唯一一条边到 a（ab）；接着第二位是点号，但站在 ab 上这条线只有一个孩子 d，分叉口里其实只有一条可走；第三位又是点号，同理走到底的 db 带词尾——命中，返回 true。这一帧把两种机制接在一条查询里：确定字母「走唯一孩子」紧接着点号「试所有孩子」，正是本题最典型的走法。

search(".at") · 三条分支全走不通 → false：再看一个返回 false 的：查 ".at"。点号同样把 b、d、m 三条分支都试一遍，每条往下第二个字母 a 都对得上，可第三个字母要 t——而这一层树里只有 d，没有 t。三条分支全部走到底却都不匹配，没有任何一个词尾被命中，所以这帧没有绿色（绿色只在「本次成功命中词尾」时才亮）。DFS 退回根、再无可试，最终返回 false。

慢放 · DFS 的「试—失败—回退—再试」：把上一帧慢放，看清 DFS 的核心节律。b 分支刚刚走到底发现第三位没有 t，失败——它和它下面的 a 不再高亮（灰掉），表示「这条试过了、回退」。回退后轮到第二条 d 分支：现在它亮成蓝色正在试（r → d1 → ad），往下第三位同样卡在没有 t，又会失败回退；最后还排队等着的 m 分支也是一样的结局。这种「试一条 → 不行 → 灰掉回退 → 换下一条」就是递归 DFS 天生擅长的回溯，对应代码里 for 循环逐个孩子 dfs、谁返回 true 就停。

一句话本质：前缀树负责存，DFS 负责查；普通字母只有一条路、点号是个分叉口。把这句记住，这道题就拿下了。

雷区实演 · 存了 bad，查 ba 为什么是 false：把雷区一在这棵现成的树上真跑一遍：存过 bad，现在查 ba。b → a 这条路确实走得通（r → b → ab 都点亮了），ba 在树里是一段真实存在的前缀。但关键看终点 ab 这个 a 节点——它只是 bad 半路上的字母，词尾标记长在再往下的 db 上（图里那个绿色的 d 才是 bad 的真正词尾），ab 自己没有词尾标记（它没亮绿，只是蓝色的「到达点」）。所以 dfs 在末尾检查 node.end 时得到 false：路径在 ≠ 存过这个词。这正是「忘查词尾」会翻车的根因——画出来一眼就懂。

边界三连：三个边界把雷区演成了真用例：全是点最费、词尾标记决定 ba 这种「半截路径」该返回 false。

三个高频追问：与 LC208 的区别、为何用 DFS、以及换成星号通配会怎样。