leetcode-211. 添加与搜索单词

技术leetcode-211. 添加与搜索单词 leetcode-211. 添加与搜索单词 - 数据结构设计leetcode-211. 添加与搜索单词 - 数据结构设计
题目:
请你设计一个数据结构,支

Leetcode-211。添加和搜索单词-数据结构设计。

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

题目:

请设计一个支持添加新单词的数据结构,并找出字符串是否匹配任何以前添加的字符串。

实现字典类单词字典:

WordDictionary()初始化字典对象。

空添加单词(word)将单词添加到数据结构中,然后就可以匹配了。

如果数据结构中的字符串与word匹配,Bool search(word)返回true否则,返回false。单词可能包含一些“.”,和每个。可以代表任何字母。

思路:

Ontology直接将所有单词存储在数组中,在搜索时遍历所有单词,但这种代码搜索效率低,可能会超时,所以我们可以根据代码对单词进行分类,并存储在map int mapint、vectorstring的数据结构中,其中map的关键是长度,值是对应长度的单词。插入单词时,先计算单词长度,然后再将其插入相应的数组。搜索时,直接根据字长找到对应的集合,遍历集合中的所有单词,然后进行逐字符匹配。如果是“.”,跳过这一次,如果匹配成功,则返回true。

这个问题也可以通过前缀树来解决,因为只有26个单词,所以构造的字典树是一个26分支的树,并且设置了一个标志isEnd来记录这个字母是否是单词的结尾。

数据结构:

类TrieNode{

公众号:

//存储子节点。

vectorTrieNode *子级;

//结束符号。

bool isEnd

TrieNode(){ 0

//初始化子节点。

child=vectorTrieNode * { 26,nullptr };

//默认设置为false,插入时将最后一个字母的标志设置为true。

isEnd=false

};

};

插入元素时,单词通过遍历合并到前缀树中。

当寻找元素时,

如果遍历到单词的末尾,则表示该单词匹配成功,并返回true。

如果单个当前字母为a-z,则递归判断trie-child[word[i]-'a']和word[i 1:]的查询结果。

如果当前遍历的字母是“.”,需要递归搜索每个子节点。

Code

地图收藏

类单词词典(}

公众号:

mapint,vectorstring m;

word dictionary(){ 0

}

void addWord(字符串单词){ 0

if(m . count(word . size())==0){ 0

vectorstring cur={ word };

m[word . size()]=cur;

}

else{

m[word.size()]。push_back(单词);

}

}

bool搜索(字符串)

int len=word . size();

if(m . count(len)=0)

返回false

}

for(auto item :m[word . size()]){ 0

bool have=true

for(int I=0;伊琳;I){ 0

if(word[i]!='.'字[我]!=项目[I]){ 0

have=false

}

}

如果有

返回真;

}

}

返回false

}

};

前缀树

类TrieNode{

公众号:

vectorTrieNode *子级;

bool isEnd

TrieNode(){ 0

child=vectorTrieNode * { 26,nullptr };

isEnd=false

};

};

类单词词典(}

公众号:

TrieNode * root

word dictionary(){ 0

root=new TrieNode();

}

void addWord(字符串单词){ 0

TrieNode * cur=root

for(int I=0;iword . size();I){ 0

if(cur-child[word[I]-' a ']==nullptr){ 0

cur-child[word[I]-' a ']=new TrieNode();

}

cur=cur-child[word[I]-' a '];

}

//结束标志设置为真。

cur-isEnd=true;

};

bool搜索(字符串)

TrieNode * cur=root

//递归查询

返回dfs(cur,0,word);

};

bool dfs(TrieNode* root,int inx,string word){ 0

//找到最后。

if(inx==word . size()){ 0

返回root-isEnd;

};

//当你遇到“.”,您需要遍历所有26个字母一次。

if(word[inx]==' . '){

for(int I=0;i26I){ 0

if(root-child[i]!=nullptr dfs(根-子[i],inx 1,word)){ 0

返回真;

}

}

返回false

}

else{

if(root-child[word[inx]-'a']!=nullptr dfs(根-子[word[inx]-'a'],inx 1,word)){ 0

返回真;

}

返回错误的

};

};

};

内容来源网络,如有侵权,联系删除,本文地址:https://www.230890.com/zhan/37487.html

(0)

相关推荐

  • php_vld怎么用

    技术php_vld怎么用这篇文章主要为大家展示了“php_vld怎么用”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“php_vld怎么用”这篇文章吧。

    攻略 2021年12月10日
  • Elasticsearch Java Client版本区别及起步是什么

    技术Elasticsearch Java Client版本区别及起步是什么这期内容当中小编将会给大家带来有关Elasticsearch Java Client版本区别及起步是什么,文章内容丰富且以专业的角度为大家分析和叙

    攻略 2021年10月19日
  • sparkstreaming统计(sparkstream实时计算结果)

    技术SparkStreaming算子开发实例分析本篇文章为大家展示了SparkStreaming算子开发实例分析,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。Spark Stre

    攻略 2021年12月17日
  • 怎么画中国地图,晚清中国地图是如何绘制的

    技术怎么画中国地图,晚清中国地图是如何绘制的清朝的地图绘制有三种方法,第一种是传统绘制法,以“计里画方”法(方里网法)为主怎么画中国地图;第二种是西方经纬网法;第三种是双重网格法。“计里画方”法,实质是地图投影中的方格投

    生活 2021年11月1日
  • jsp报错问题汇总

    技术jsp报错问题汇总 jsp报错问题汇总一、jsp 页面跳转报错c:forEach items="${map}" var="m"%--取出map的key和value,JSTL提供了一下方式--%${m

    礼包 2021年11月1日
  • 双网卡问题

    技术双网卡问题 双网卡问题目录双网卡问题问题问题一问题二总结问题三
    双网卡问题
    问题环境介绍:
    如上图所示,PC-A有两卡网卡,注意,网卡一设置有默认网关,而网卡二并没有,网卡二只有IP和掩码,网卡的默

    礼包 2021年11月27日