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

返回真；

}

返回错误的

};

};

};