MediumBlind75StringTrieDFSDesign
Design Add and Search Words Data Structure
Design a data structure that supports adding new words and finding if a string matches any previously added string. The word may contain dots '.' that can match any letter.
Examples
Input
wordDictionary.addWord('bad'); wordDictionary.search('bad'); wordDictionary.search('.ad'); wordDictionary.search('b..')Output
true, true, true
'bad' matches 'bad', '.ad' matches 'bad', 'b..' matches 'bad'.
Input
wordDictionary.addWord('dad'); wordDictionary.search('pad')Output
false
'pad' does not match any added word.
Constraints
- •
1 <= word.length <= 25 - •
word in addWord consists lowercased English letters. - •
word in search consist of '.' or lowercase English letters. - •
There will be at most 3 dots in word for search queries. - •
At most 10^4 calls will be made to addWord and search.
Approaches
Store all words in a list, search by checking each word.
CodeT: O(n * m) | S: O(n * m)
class WordDictionary:
def __init__(self):
self.words = []
def addWord(self, word):
self.words.append(word)
def search(self, word):
for w in self.words:
if len(w) != len(word):
continue
match = True
for i in range(len(w)):
if word[i] != '.' and w[i] != word[i]:
match = False
break
if match:
return True
return FalseUse a trie for storage and DFS for search with wildcards.
CodeT: O(m) add, O(26^n) worst search | S: O(m)
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
def dfs(node, idx):
if idx == len(word):
return node.is_end
if word[idx] == '.':
for child in node.children.values():
if dfs(child, idx + 1):
return True
return False
if word[idx] not in node.children:
return False
return dfs(node.children[word[idx]], idx + 1)
return dfs(self.root, 0)Same approach with memoization potential.
Diagram
addWord('bad'): root->b->a->d(is_end)
search('.ad'): '.' matches any, try b->a->d -> True
search('b..'): b matches, '..' matches a,d -> True
search('pad'): p not in root.children -> False
CodeT: O(m) add, O(26^n) worst search | S: O(m)
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
node = self.root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.is_end = True
def search(self, word):
stack = [(self.root, 0)]
while stack:
node, idx = stack.pop()
if idx == len(word):
if node.is_end:
return True
continue
if word[idx] == '.':
for child in node.children.values():
stack.append((child, idx + 1))
elif word[idx] in node.children:
stack.append((node.children[word[idx]], idx + 1))
return FalseComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force - Linear Scan | O(n * m) | O(n * m) | Store all words in a list, search by checking each word. |
| Trie with DFS | O(m) add, O(26^n) worst search | O(m) | Use a trie for storage and DFS for search with wildcards. |
| Optimized Trie DFS | O(m) add, O(26^n) worst search | O(m) | Same approach with memoization potential. |
Brute Force - Linear Scan
T: O(n * m)S: O(n * m)
Store all words in a list, search by checking each word.
Trie with DFS
T: O(m) add, O(26^n) worst searchS: O(m)
Use a trie for storage and DFS for search with wildcards.
Optimized Trie DFS
T: O(m) add, O(26^n) worst searchS: O(m)
Same approach with memoization potential.
Common Mistakes
Not handling the '.' wildcard correctly
Using recursion without early termination
Not marking the end of complete words