0%

[Leetcode]211. Add and Search Word - Data structure design

题目描述

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

这道题由于存在通配符 . 所以需要考虑额外的情况。我首先想到的是利用一个队列维护当前层的节点和下一层的节点,遇到 . 的时候将当前节点的下一层全部推入下一层要搜索的节点,相当于一种层序遍历的思路,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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 上超时了,想了一下原因大概是因为层序遍历的原因,虽然避免了递归产生的空间消耗,但是不能优先搜索某一条路径,应该用前序遍历的思路来做,修改代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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(树节点个数)