百度收录网站中文称仙桃网站制作州国

百度收录网站中文称,仙桃网站制作州国,做淘宝客需要自己建网站吗,58网站怎么做品牌推广在LeetCode的字符串类题目中#xff0c;“添加与搜索单词”是一道经典的设计题#xff0c;核心考察**字典树#xff08;Trie#xff09;**的应用#xff0c;同时结合深度优先搜索#xff08;DFS#xff09;解决通配符匹配问题。这道题不仅能帮我们掌握字典树的基本操作privateisEnd:boolean;constructor(){this.children{};// 存储子节点key为字符value为子节点this.isEndfalse;// 标记当前节点是否是单词结尾}addWord(word:string):void{letnode:WordDictionarythis;// 从根节点开始遍历for(constchofword){// 如果当前字符对应的子节点不存在创建新节点if(!node.children[ch]){node.children[ch]newWordDictionary();}// 移动到子节点继续处理下一个字符nodenode.children[ch];}// 单词遍历结束标记当前节点为单词结尾node.isEndtrue;}search(word:string):boolean{// 深度优先搜索index表示当前匹配到的单词下标node表示当前遍历的字典树节点constdfs(index:number,node:WordDictionary):boolean{// 递归终止条件匹配完所有字符判断当前节点是否是单词结尾if(indexword.length){returnnode.isEnd;}constchword[index];// 情况1当前字符不是通配符精确匹配if(ch!.){constchildnode.children[ch];// 子节点存在且递归匹配下一个字符成功返回trueif(childdfs(index1,child)){returntrue;}}else{// 情况2当前字符是通配符遍历所有子节点尝试匹配for(conststrinnode.children){constchildnode.children[str];// 任意一个子节点递归匹配成功就返回trueif(childdfs(index1,child)){returntrue;}}}// 以上情况都不满足匹配失败returnfalse;}// 从根节点、下标0开始DFSreturndfs(0,this);}}/** * Your WordDictionary object will be instantiated and called as such: * var obj new WordDictionary() * obj.addWord(word) * var param_2 obj.search(word) */四、核心方法拆解1. 构造函数constructor初始化字典树的根节点children用对象Record存储子节点键是字符如’a’、‘b’值是子节点实例这样可以快速通过字符定位子节点isEnd初始化为false因为根节点本身不代表任何单词的结尾。2. 添加单词addWord方法添加单词的逻辑本质是“构建字典树”步骤如下从根节点this开始遍历单词的每一个字符对于当前字符如果当前节点的children中没有该字符对应的子节点就创建一个新的WordDictionary实例作为子节点将当前节点移动到该子节点继续处理下一个字符当单词遍历完毕将最后一个节点的isEnd设为true标记这是一个完整单词的结尾。示例添加单词apple会从根节点开始依次创建’a’、‘p’、‘p’、‘l’、e’对应的节点最后将’e’节点的isEnd设为true。3. 搜索单词search方法搜索单词是本题的核心由于存在通配符.我们采用**深度优先搜索DFS**来处理所有可能的匹配情况核心逻辑分为两部分1DFS辅助函数定义一个内部DFS函数接收两个参数index当前匹配到单词的第几个字符从0开始node当前遍历到字典树的哪个节点。递归终止条件当index等于单词长度时说明已经匹配完所有字符此时只需判断当前节点的isEnd是否为true即是否是一个完整单词。2两种匹配情况精确匹配当前字符不是’.检查当前节点的children中是否存在该字符对应的子节点如果存在递归调用DFS处理下一个字符index1并将当前子节点作为新的node如果子节点不存在或递归匹配失败继续判断其他情况最终返回false。通配符匹配当前字符是’.通配符可以匹配任意字符因此需要遍历当前节点的所有子节点对每个子节点递归调用DFS处理下一个字符只要有一个子节点递归匹配成功就直接返回true剪枝优化避免不必要的遍历。示例搜索ap.ple当遍历到第3个字符.时会遍历当前节点第二个’p’的所有子节点只要有一个子节点此处是’l’能继续匹配后续字符就返回true。五、易错点与优化思路1. 易错点总结忘记标记isEnd添加单词时如果不将最后一个节点的isEnd设为true会导致搜索时无法区分“前缀”和“完整单词”例如添加app后搜索app会返回falseDFS递归终止条件错误终止条件必须是index word.length而不是node.children为空否则会漏掉“单词长度与路径长度一致但不是结尾”的情况通配符遍历遗漏遍历子节点时要确保遍历所有children中的键不能遗漏任何一种可能的字符。2. 优化思路空间优化如果单词集合中重复前缀较少字典树的空间优势不明显可以考虑结合哈希表分组按单词长度分组搜索时先根据长度过滤再进行匹配减少DFS的次数时间优化在DFS中加入剪枝逻辑一旦找到匹配的子节点立即返回true避免不必要的遍历边界处理针对空字符串、单个字符、全通配符如....等边界情况提前做判断提升效率。六、总结LeetCode 211题的核心是“字典树DFS”的组合应用字典树负责高效存储和快速定位字符串前缀DFS负责处理通配符带来的模糊匹配问题。通过这道题我们不仅掌握了字典树的基本操作添加、遍历还理解了递归在复杂匹配场景中的应用逻辑。其实字典树的应用非常广泛比如搜索引擎的自动补全、拼写检查、IP路由最长前缀匹配等场景掌握这道题的思路能为后续解决类似的字符串匹配问题打下坚实的基础。