题目描述
Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters
a-z
or.
. A.
means it can represent any one letter.
例子
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note
You may assume that all words are consist of lowercase letters a-z.
解题思路
这道题很显然是用 Trie 来做,Trie 基本概念参见 维基百科-Trie。
这道题由于存在通配符 .
所以需要考虑额外的情况。我首先想到的是利用一个队列维护当前层的节点和下一层的节点,遇到 .
的时候将当前节点的下一层全部推入下一层要搜索的节点,相当于一种层序遍历的思路,代码如下:
class WordDictionary {
public:
/** Initialize your data structure here. */
WordDictionary() {
head = std::make_shared<TreeNode>();
}
/** Adds a word into the data structure. */
void addWord(string word) {
std::shared_ptr<TreeNode> current_node = head;
for (char c: word) {
int index = c - 'a';
if (current_node->next_levels[index] == nullptr) {
current_node->next_levels[index] = std::make_shared<TreeNode>();
}
current_node = current_node->next_levels[index];
}
current_node->is_word = 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) {
std::vector<std::shared_ptr<TreeNode>> current_nodes{head};
for (char c: word) {
std::vector<std::shared_ptr<TreeNode>> next_nodes;
int index = c - 'a';
for (const auto& current_node: current_nodes) {
if (c == '.') {
for (const auto next_node: current_node->next_levels) {
if (next_node) {
next_nodes.push_back(next_node);
}
}
}
else if (current_node->next_levels[index]) {
next_nodes.push_back(current_node->next_levels[index]);
}
}
current_nodes = next_nodes;
if (current_nodes.empty()) break;
}
for (const auto& current_node: current_nodes) {
if (current_node->is_word) return true;
}
return false;
}
private:
struct TreeNode {
bool is_word;
std::vector<std::shared_ptr<TreeNode>> next_levels;
TreeNode() {
is_word = false;
next_levels = std::vector<std::shared_ptr<TreeNode>>(26, nullptr);
}
};
std::shared_ptr<TreeNode> head;
};
这种方法在 leetcode 上超时了,想了一下原因大概是因为层序遍历的原因,虽然避免了递归产生的空间消耗,但是不能优先搜索某一条路径,应该用前序遍历的思路来做,修改代码如下:
class WordDictionary {
public:
/** Initialize your data structure here. */
WordDictionary() {
head = std::make_shared<TreeNode>();
}
/** Adds a word into the data structure. */
void addWord(string word) {
std::shared_ptr<TreeNode> current_node = head;
for (char c: word) {
int index = c - 'a';
if (current_node->next_levels[index] == nullptr) {
current_node->next_levels[index] = std::make_shared<TreeNode>();
}
current_node = current_node->next_levels[index];
}
current_node->is_word = 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 searchAletter(head, word, 0);
}
private:
struct TreeNode {
bool is_word;
std::vector<std::shared_ptr<TreeNode>> next_levels;
TreeNode() {
is_word = false;
next_levels = std::vector<std::shared_ptr<TreeNode>>(26, nullptr);
}
};
bool searchAletter(const std::shared_ptr<TreeNode> node, const string& word, int index) {
if (node == nullptr) return false;
if (index == word.length()) return node->is_word;
char character = word[index];
if (character == '.') {
for (int i = 0; i < 26; i++) {
if (searchAletter(node->next_levels[i], word, index + 1)) return true;
}
return false;
}
return searchAletter(node->next_levels[character - 'a'], word, index + 1);
}
std::shared_ptr<TreeNode> head;
};
- 时间复杂度: n 为 字符串长度
- 添加:O(n)
- 搜索:
- 没有
.
:O(n) - 有
.
:O(树节点个数)
- 没有