LeetCode 211. 添加与搜索单词 - 数据结构设计思路使用 Trie前缀树 存储单词。addWord 正常插入search 遇到普通字母沿对应子节点走遇到 . 则遍历所有非空子节点递归匹配。Java 实现classWordDictionary{privatestaticclassTrieNode{TrieNode[]childrennewTrieNode[26];booleanisEnd;}privateTrieNoderoot;publicWordDictionary(){rootnewTrieNode();}publicvoidaddWord(Stringword){TrieNodenoderoot;for(charc:word.toCharArray()){intidxc-a;if(node.children[idx]null){node.children[idx]newTrieNode();}nodenode.children[idx];}node.isEndtrue;}publicbooleansearch(Stringword){returndfs(word,0,root);}privatebooleandfs(Stringword,intindex,TrieNodenode){if(nodenull){returnfalse;}// 单词已遍历完判断当前节点是否是某个单词结尾if(indexword.length()){returnnode.isEnd;}charcword.charAt(index);if(c.){// . 可以匹配任意一个字母尝试所有存在的分支for(inti0;i26;i){if(node.children[i]!nulldfs(word,index1,node.children[i])){returntrue;}}returnfalse;}else{// 普通字母沿对应子节点继续匹配intidxc-a;returndfs(word,index1,node.children[idx]);}}}复杂度分析· addWordO(L)L 为单词长度。· search· 最好情况O(L)没有 . 或 . 很少。· 最坏情况O(26^L) 或 O(总节点数)当查询全是 . 时会遍历大量分支。· 空间O(N × L)N 为插入单词数L 为平均长度即 Trie 中所有节点总数。关键点Trie 节点用 TrieNode[26] 数组存子节点下标 c - ‘a’比 HashMap 更快但稍占空间。. 的处理在 dfs 中遇到 . 时遍历当前节点的所有非空子节点只要有一条路径能匹配成功就返回 true。递归终止条件index word.length() 时必须判断 node.isEnd而不是直接返回 true否则会误匹配前缀。剪枝. 分支只递归非空子节点避免无效搜索。该实现可直接在 LeetCode 211 题中通过。