【leetcode】211. Add and Search Word - Data structure design
程序员文章站
2022-05-18 10:04:08
...
题目:
思路:
数据结构与【leetcode】208. Implement Trie (Prefix Tree)是一样的,只是search函数从迭代的方式改成了递归的方式,因为遇到字符“.”会涉及到回溯。
我又对此数据结构的存储细节进行了剖析,以“dad”为例,其的存储结构如下图:
代码实现:
class TrieNode{
public:
TrieNode *child[26];
TrieNode():isWord(false){
for (auto &a : child){
a = nullptr;
}
}
bool isWord; // 如果此节点最后一个字符,则说明到此为止是一个完整的单词。
};
class WordDictionary {
private:
TrieNode *root;
public:
/** Initialize your data structure here. */
WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
void addWord(string word) {
TrieNode *p = root;
for (auto &c : word){
int i = c - 'a';
if (p->child[i] == nullptr){
p->child[i] = new TrieNode();
}
p = p->child[i];
}
p->isWord = true;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
bool search(string word) {
return f(word, 0, root);
}
bool f(string &word, int w_i, TrieNode* p){
if (w_i >= word.size()){
return p->isWord;
}
if (word[w_i] == '.'){
for (int i = 0; i < 26; ++i){
if (p->child[i]){
if (f(word, w_i+1, p->child[i])){
return true;
}
}
}
}else{
if (p->child[word[w_i]-'a'] == nullptr){
return false;
}
return f(word, w_i+1, p->child[word[w_i]-'a']);
}
return false;
}
};
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary* obj = new WordDictionary();
* obj->addWord(word);
* bool param_2 = obj->search(word);
*/
推荐阅读
-
【leetcode】211. Add and Search Word - Data structure design
-
LeetCode-211. Add and Search Word - Data structure design(字典树和递归)
-
【Leetcode&C语言&Tire】208.Implement Trie (Prefix Tree) & 211.Design Add and Search Words Data Structure
-
211. Add and Search Word - Data structure design(难啊)
-
Add and Search Word - Data structure design