211. Add and Search Word – Data structure design
- Total Accepted: 37880
- Total Submissions: 188966
- Difficulty: Medium
- Contributors: Admin
Design a data structure that supports the following two operations:
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.
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.
You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.
Code
class TrieNode():
def __init__(self):
self.nodes = {}
self.isword = False
class WordDictionary(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.root = TrieNode()
def addWord(self, word):
"""
Adds a word into the data structure.
:type word: str
:rtype: void
"""
root = self.root
for i, ch in enumerate(word):
if not root.nodes.get(ch, None):
root.nodes[ch] = TrieNode()
root = root.nodes[ch]
if i == len(word) - 1:
root.isword = True
def search(self, word):
"""
Returns if the word is in the data structure. A word could
contain the dot character '.' to represent any one letter.
:type word: str
:rtype: bool
"""
assert len(word) > 0
return self.search_helper(word, 0, self.root)
def search_helper(self, word, idx, root):
ch = word[idx]
if ch == '.':
if idx == len(word) - 1:
return any(map(lambda x: x.isword, root.nodes.values()))
else:
return any(map(lambda x: self.search_helper(word, idx+1, x), root.nodes.values()))
else:
if root.nodes.get(ch, None) is None:
return False
else:
if idx == len(word) - 1:
return root.nodes[ch].isword
else:
return self.search_helper(word, idx+1, root.nodes[ch])
# Your WordDictionary object will be instantiated and called as such:
# wordDictionary = WordDictionary()
# wordDictionary.addWord("word")
# wordDictionary.search("pattern")
Idea
Use Trie structure to store words and make search. Assume we have O(N) words and each word has O(K) length. Then each add takes O(K) time and O(K) space. Each search takes O(K) time . See another post: https//nb4799.neu.edu/wordpress/?p=1162