211 Add and Search Word - Data structure design

1. Question

Design a data structure that supports the following two operations:
1
void addWord(word)
2
bool search(word)
Copied!
search(word) can search a literal word or a regular expression string containing only lettersa-zor.. A.means it can represent any one letter.
For example:
1
addWord("bad")
2
addWord("dad")
3
addWord("mad")
4
search("pad") -> false
5
search("bad") -> true
6
search(".ad") -> true
7
search("b..") -> true
Copied!
Note: You may assume that all words are consist of lowercase lettersa-z.

2. Implementation

(1) Trie + Backtracking
1
class WordDictionary {
2
class TrieNode {
3
char val;
4
boolean isWord;
5
TrieNode[] childNode;
6
7
public TrieNode(char val) {
8
this.val = val;
9
childNode = new TrieNode[26];
10
}
11
}
12
13
TrieNode root;
14
15
/** Initialize your data structure here. */
16
public WordDictionary() {
17
root = new TrieNode(' ');
18
}
19
20
/** Adds a word into the data structure. */
21
public void addWord(String word) {
22
if (word == null || word.length() == 0) {
23
return;
24
}
25
26
TrieNode curNode = root;
27
28
for (char c : word.toCharArray()) {
29
int index = c - 'a';
30
31
if (curNode.childNode[index] == null) {
32
curNode.childNode[index] = new TrieNode(c);
33
}
34
curNode = curNode.childNode[index];
35
}
36
curNode.isWord = true;
37
}
38
39
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
40
public boolean search(String word) {
41
if (word == null || word.length() == 0) {
42
return false;
43
}
44
45
return searchByDFS(root, 0, word);
46
}
47
48
public boolean searchByDFS(TrieNode node, int depth, String word) {
49
if (depth == word.length()) {
50
return node.isWord;
51
}
52
53
char c = word.charAt(depth);
54
55
if (c == '.') {
56
for (TrieNode childNode : node.childNode) {
57
if (childNode != null && searchByDFS(childNode, depth + 1, word)) {
58
return true;
59
}
60
}
61
return false;
62
}
63
else {
64
int index = c - 'a';
65
return node.childNode[index] != null && searchByDFS(node.childNode[index], depth + 1, word);
66
}
67
}
68
}
69
70
/**
71
* Your WordDictionary object will be instantiated and called as such:
72
* WordDictionary obj = new WordDictionary();
73
* obj.addWord(word);
74
* boolean param_2 = obj.search(word);
75
*/
Copied!

3. Time & Space Complexity

时间复杂度: insert: O(w * L), search: O(26^m), w为放在trie的word的个数,L为word的平均长度,m为查询的word的长度
空间复杂度: O(w * L)