211 Add and Search Word - Data structure design

Search…

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)

208 Implement Trie (Prefix Tree)

336 Palindrome Pairs

Last modified 2yr ago

Copy link

Contents

211. Add and Search Word - Data structure design

1. Question

2. Implementation

3. Time & Space Complexity

211. Add and Search Word - Data structure design​

1. Question

2. Implementation

3. Time & Space Complexity

211. Add and Search Word - Data structure design