企业官网建设流程全解析

黄骅网站建设价格,坂田网站建设,html菜鸟教程导航栏,wordpress工程师LeetCode 面试经典 150_字典树_添加与搜索单词 - 数据结构设计#xff08;96_211_C_中等#xff09;题目描述#xff1a;输入输出样例#xff1a;题解#xff1a;解题思路#xff1a;思路一#xff08;字典树#xff09;#xff1a;代码实现代码实现#xff08;思路一…LeetCode 面试经典 150_字典树_添加与搜索单词 - 数据结构设计96_211_C_中等题目描述输入输出样例题解解题思路思路一字典树代码实现代码实现思路一字典树题目描述请你设计一个数据结构支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。实现词典类 WordDictionary WordDictionary() 初始化词典对象void addWord(word) 将 word 添加到数据结构中之后可以对它进行匹配bool search(word) 如果数据结构中存在字符串与 word 匹配则返回 true 否则返回 false 。word中可能包含一些 ‘.’ 每个 . 都可以表示任何一个字母。输入输出样例示例 1输入[“WordDictionary”,“addWord”,“addWord”,“addWord”,“search”,“search”,“search”,“search”][[],[“bad”],[“dad”],[“mad”],[“pad”],[“bad”],[“.ad”],[“b…”]]输出[null,null,null,null,false,true,true,true]解释WordDictionary wordDictionary new WordDictionary();wordDictionary.addWord(“bad”);wordDictionary.addWord(“dad”);wordDictionary.addWord(“mad”);wordDictionary.search(“pad”); // 返回 FalsewordDictionary.search(“bad”); // 返回 TruewordDictionary.search(“.ad”); // 返回 TruewordDictionary.search(“b…”); // 返回 True提示1 word.length 25addWord 中的 word 由小写英文字母组成search 中的 word 由 ‘.’ 或小写英文字母组成最多调用 104次 addWord 和 search题解解题思路思路一字典树1、实现思路如下插入单词从左到右插入这个单词的每个字母若当前字母不存在字典树中注意child是0~25若child为nullptr则不存在创建结点若为最后一个单词则进行标记isEndtrue。查找单词因单词中包含’.,所以我们要分两种情况讨论从左到右查找这个单词的每个字符。若当前位置为字母则查找node[word[i]-‘a’]存不存在若存在则继续查找若不存在则返回false若当前位置为’.,我们需要挨个判断此节点的所有儿子结点的分支。首先此节点的儿子结点不能为nullptr其次递归的匹配其儿子结点若匹配成功则返回true否则返回false需要非常注意一点字典树的 根结点 不存储任何信息。2、复杂度分析① 时间复杂度O(26k·L假设在最坏情况下字典树的每个节点都有26个子节点如果遇到 个 “.”则为每个.都会进行 26 次递归。② 空间复杂度O(N×L)O(N×L)其中 N 是独立单词的数量L 是单词的平均长度。代码实现代码实现思路一字典树classWordDictionary{private:// 定义字典树的节点结构体TrieNodestructTrieNode{vectorTrieNode*child;// 子节点数组表示26个字母的子节点boolisEnd;// 标记当前节点是否为某个单词的结束节点TrieNode():child(26,nullptr),isEnd(false){}// 构造函数初始化子节点数组为26个nullptr并将isEnd初始化为false};TrieNode*root;// 根节点// 插入单词的函数voidinsert(TrieNode*root,conststringword){TrieNode*noderoot;// 遍历单词中的每个字符for(autoc:word){// 计算字符对应的索引并检查当前字符的子节点是否为空if(node-child[c-a]nullptr){// 如果为空说明该字符路径还没有建立创建新的节点node-child[c-a]newTrieNode();}// 将当前节点指向下一个字符的子节点nodenode-child[c-a];}// 单词遍历完成后将当前节点的isEnd标记为true表示这是一个完整的单词node-isEndtrue;}// 搜索单词的深度优先搜索DFS函数booldfs(stringword,TrieNode*node,intindex){// 如果遍历到单词的末尾返回当前节点是否为单词的结束节点if(indexword.size()){returnnode-isEnd;}// 如果当前字符是.可以匹配任意字符if(word[index].){// 遍历当前节点的所有子节点for(autochild:node-child){// 对每个非空子节点递归进行DFSif(child!nullptrdfs(word,child,index1)){returntrue;// 如果某个子节点匹配成功返回true}}returnfalse;// 如果所有子节点都无法匹配返回false}else{// 如果当前字符不是.则检查当前节点对应字符的子节点是否为空if(node-child[word[index]-a]nullptr){returnfalse;// 如果没有对应的子节点返回false}// 否则继续递归搜索下一个字符returndfs(word,node-child[word[index]-a],index1);}}public:// 构造函数初始化根节点WordDictionary(){rootnewTrieNode();}// 添加一个单词到字典中voidaddWord(string word){insert(root,word);// 调用插入函数}// 搜索单词支持.通配符boolsearch(string word){returndfs(word,root,0);// 从根节点开始递归DFS}};LeetCode 面试经典 150_字典树_添加与搜索单词 - 数据结构设计96_211原题链接欢迎大家和我沟通交流(✿◠‿◠)