211. Add and Search Word - Data structure design
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.
Solution: Trie
class WordDictionary(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.trie = dict()
def addWord(self, word):
"""
Adds a word into the data structure.
:type word: str
:rtype: void
"""
node = self.trie
for char in word:
if char not in node:
node[char] = dict()
node = node[char]
node['#'] = None
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
"""
def dfs(idx, node):
if idx == len(word):
return '#' in node
char = word[idx]
if char == '.':
return any(dfs(idx + 1, val) for val in node.values() if val)
if char in node:
return dfs(idx + 1, node[char])
return False
return dfs(0, self.trie)
Lessons:
- When we see
., skip current level, recursively search next level.