LeetCode 211. 添加与搜索单词 - 数据结构设计
原题链接
中等
作者:
我是java同学
,
2023-10-14 15:39:00
,
所有人可见
,
阅读 45
class WordDictionary {
public:
struct Node {
bool is_end;
Node* son[26];
Node() {
is_end = false;
for (int i = 0; i < 26; i ++ )
son[i] = NULL;
}
}* root;
WordDictionary() {
root = new Node();
}
void addWord(string word) {
auto p = root;
for (int i = 0; i < word.size(); i ++ ) {
int u = word[i] - 'a';
if (!p->son[u]) p->son[u] = new Node();
p = p->son[u];
}
p->is_end = true;
}
bool search(string word) {
return dfs(word, root, 0);
}
bool dfs(string& word, Node* p, int i) {
if (i == word.size()) return p->is_end;
if (word[i] == '.') {
for (int j = 0; j < 26; j ++ )
if (p->son[j] && dfs(word, p->son[j], i + 1))
return true;
return false;
} else {
int u = word[i] - 'a';
if (!p->son[u]) return false;
return dfs(word, p->son[u], i + 1);
}
}
};
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary* obj = new WordDictionary();
* obj->addWord(word);
* bool param_2 = obj->search(word);
*/