Design a data structure that supports the following two operations: addWord(word) and 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.

Notice
You may assume that all words are consist of lowercase letters a-z.

Example

1
2
3
4
5
6
7
addWord("bad")
addWord("dad")
addWord("mad")
search("pad")  // return false
search("bad")  // return true
search(".ad")  // return true
search("b..")  // return true

典型的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
public class WordDictionary {
    class TrieNode {
        char c;
        HashMap<Character, TrieNode> children = new HashMap<>();
        boolean isWord = false;
        public TrieNode(char c) {
            this.c = c;
        }
    }
    
    TrieNode root = new TrieNode('#');
    public void addWord(String word) {
        TrieNode parent = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!parent.children.containsKey(c)) {
                parent.children.put(c, new TrieNode(c));
            }
            parent = parent.children.get(c);
        }
        parent.isWord = true;
    }
    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        ArrayList<TrieNode> parents = new ArrayList<>();
        parents.add(root);
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            ArrayList<TrieNode> newparents = new ArrayList<>();
            if (c == '.') {
                for (TrieNode parent : parents) {
                    for (Map.Entry<Character, TrieNode> entry : parent.children.entrySet()) {
                        newparents.add(entry.getValue());
                    }
                }
            } else {
                for (TrieNode parent : parents) {
                    if (parent.children.containsKey(c)) {
                        newparents.add(parent.children.get(c));
                    }
                }
            }
            parents = newparents;
        }
        for (TrieNode parent : parents) {
            if (parent.isWord)
                return true;
        }
        return false;
    }
}