211. Add and Search Word - Data structure design

  • 21.1%

Design a data structure that supports the following two operations:

1
2
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.

1
2
3
4
5
6
7
8
9
For example:

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.

click to show hint.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.


https://discuss.leetcode.com/topic/15581/80ms-clear-c-code-with-detailed-explanations

80ms Clear C++ Code with Detailed Explanations

This problem is an application of the Trie data structure. In the following, it is assumed that you have solved Implement Trie (Prefix Tree).

Now, let’s first look at the TrieNode class. I define it as follows.

1
2
3
4
5
6
7
8
class TrieNode {
public:
bool isKey;
TrieNode* children[26];
TrieNode(): isKey(false) {
memset(children, NULL, sizeof(TrieNode*) * 26);
}
};

The field isKey is to label whether the string comprised of characters starting from root to the current node is a key (word that has been added). In this problem, only lower-case letters a - z need to be considered, so each TrieNode has at most 26 children. I store it in an array of TrieNode*: children[i] corresponds to letter ‘a’ + i. The remaining code defines the constructor of the TrieNode class.

Adding a word can be done in the same way as in Implement Trie (Prefix Tree). The basic idea is to create a TrieNode corresponding to each letter in the word. When we are done, label the last node to be a key (set isKey = true). The code is as follows.

1
2
3
4
5
6
7
8
9
void addWord(string word) {
TrieNode* run = root;
for (char c : word) {
if (!(run -> children[c - 'a']))
run -> children[c - 'a'] = new TrieNode();
run = run -> children[c - 'a'];
}
run -> isKey = true;
}

By the way, root is defined as private data of WordDictionary:

1
2
private:
TrieNode* root;

And the WordDictionary class has a constructor to initialize root:

1
2
3
WordDictionary() {
root = new TrieNode();
}

Now we are left only with search. Let’s do it. The basic idea is still the same as typical search operations in a Trie. The critical part is how to deal with the dots .. Well, my solution is very naive in this place. Each time when we reach a ., just traverse all the children of the current node and recursively search the remaining substring in word starting from that children. So I define a helper function query for search that takes in a string and a starting node. And the initial call to query is like query(word, root).

By the way, I pass a char* instead of string to query and it greatly speeds up the code. So the initial call to query is actually query(word.c_str(), root).

Now I put all the codes together below. Hope it to be useful!

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
class TrieNode {
public:
bool isKey;
TrieNode* children[26];
TrieNode(): isKey(false) {
memset(children, NULL, sizeof(TrieNode*) * 26);
}
};

class WordDictionary {
public:
WordDictionary() {
root = new TrieNode();
}

// Adds a word into the data structure.
void addWord(string word) {
TrieNode* run = root;
for (char c : word) {
if (!(run -> children[c - 'a']))
run -> children[c - 'a'] = new TrieNode();
run = run -> children[c - 'a'];
}
run -> isKey = 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 query(word.c_str(), root);
}

private:
TrieNode* root;

bool query(const char* word, TrieNode* node) {
TrieNode* run = node;
for (int i = 0; word[i]; i++) {
if (run && word[i] != '.')
run = run -> children[word[i] - 'a'];
else if (run && word[i] == '.') {
TrieNode* tmp = run;
for (int j = 0; j < 26; j++) {
run = tmp -> children[j];
if (query(word + i + 1, run))
return true;
}
}
else break;
}
return run && run -> isKey;
}
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

https://discuss.leetcode.com/topic/18578/c-using-trie-and-dfs-for-search-easy-understand-solution

C++ using Trie and DFS for search. easy understand solution

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
struct Trie {
vector<Trie *> child;
bool isWord;
Trie() : isWord(false), child(vector<Trie *>(26, nullptr)) {}
};
Trie *root;
WordDictionary() : root(new Trie()) {}

void addWord(string word) {
const int size_w = word.size();
Trie *cur = root;
for (int i = 0; i < size_w; i++) {
int index = word[i] - 'a';
if (!cur->child[index]) cur->child[index] = new Trie();
cur = cur->child[index];
}
cur->isWord = true;
}

bool search(string word) {
return search(word.c_str(), root);
}
bool search(const char *ch, TrieNode *cur) {
if (!cur) return false;
if (*ch == '\0') return cur->isWord;
if (*ch != '.') {
return search(ch+1, cur->child[*ch - 'a']);
} else {
for (int i = 0; i <= 25; i++) {
if (search(ch+1, cur->child[i])) return true;
}
return false;
}
}

https://discuss.leetcode.com/topic/29809/python-168ms-beat-100-solution

Python 168ms-beat-100% solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class WordDictionary(object):
def __init__(self):
self.word_dict = collections.defaultdict(list)


def addWord(self, word):
if word:
self.word_dict[len(word)].append(word)

def search(self, word):
if not word:
return False
if '.' not in word:
return word in self.word_dict[len(word)]
for v in self.word_dict[len(word)]:
# match xx.xx.x with yyyyyyy
for i, ch in enumerate(word):
if ch != v[i] and ch != '.':
break
else:
return True
return False

The search function could be done in a more pythonic way, but I see that performance has suffered so I just wrote the raw logic by myself.


https://discuss.leetcode.com/topic/14216/tree-solutions-18-20-lines

Tree solutions, 18-20 lines

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class WordDictionary:

def __init__(self):
self.root = {}

def addWord(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node[None] = None

def search(self, word):
def find(word, node):
if not word:
return None in node
char, word = word[0], word[1:]
if char != '.':
return char in node and find(word, node[char])
return any(find(word, kid) for kid in node.values() if kid)
return find(word, self.root)

An iterative alternative for the search method:

1
2
3
4
5
6
7
8
def search(self, word):
nodes = [self.root]
for char in word:
nodes = [kid
for node in nodes
for key, kid in node.items()
if char in (key, '.') and kid]
return any(None in node for node in nodes)

And one that’s a bit longer but faster:

1
2
3
4
5
6
7
def search(self, word):
nodes = [self.root]
for char in word:
nodes = [kid for node in nodes for kid in
([node[char]] if char in node else
filter(None, node.values()) if char == '.' else [])]
return any(None in node for node in nodes)

And a neat version where I append my end-marker to the word to simplify the final check:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class WordDictionary:

def __init__(self):
self.root = {}

def addWord(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node['$'] = None

def search(self, word):
nodes = [self.root]
for char in word + '$':
nodes = [kid for node in nodes for kid in
([node[char]] if char in node else
filter(None, node.values()) if char == '.' else [])]
return bool(nodes)

https://discuss.leetcode.com/topic/26944/python-solution-recursive-version-dfs

Python solution recursive version (DFS)

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
class TrieNode(object):

def __init__(self):
self.word = False
self.children = {}
class WordDictionary(object):

def __init__(self):
self.root = TrieNode()

def addWord(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = True

def search(self, word):
return self.searchFrom(self.root, word)

def searchFrom(self, node, word):
for i in xrange(len(word)):
c = word[i]
if c == '.':
for k in node.children:
if self.searchFrom(node.children[k], word[i+1:]):
return True
return False
elif c not in node.children:
return False
node = node.children[c]
return node.word
谢谢你,可爱的朋友。