Add and search word - data structure design#

Levels: level-4

Data structures: trie

Patterns: backtracking

Practice Link#

Description#

Design a data structure that supports the following two operations:
```
1void addWord(word)
2bool 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.
You may assume that all words are consist of lowercase letters a-z.

Example#

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

Python Solution#

 1import collections
 2
 3
 4class TrieNode():
 5    def __init__(self):
 6        self.children = collections.defaultdict(TrieNode)
 7        self.isWord = False
 8
 9
10class WordDictionary(object):
11    def __init__(self):
12        """
13        Initialize your data structure here.
14        """
15        self.root = TrieNode()
16
17    def addWord(self, word):
18        """
19        Adds a word into the data structure.
20        :type word: str
21        :rtype: None
22        """
23        node = self.root
24        for w in word:
25            node = node.children[w]
26        node.isWord = True
27
28    def search(self, word):
29        """
30        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
31        :type word: str
32        :rtype: bool
33        """
34        node = self.root
35        self.res = False
36        self.dfs(node, word)
37        return self.res
38
39    def dfs(self, node, word):
40        if not word:
41            if node.isWord:
42                self.res = True
43            return
44        if word[0] == ".":
45            for n in node.children.values():
46                self.dfs(n, word[1:])
47        else:
48            node = node.children.get(word[0])
49            if not node:
50                return
51            self.dfs(node, word[1:])
52
53
54# Your WordDictionary object will be instantiated and called as such:
55# obj = WordDictionary()
56# obj.addWord(word)
57# param_2 = obj.search(word)