Design Add and Search Words Data Structure
- 2 min read
- Trie
- LC-Medium
3 years ago
Solution
- Almost the same as Implement Trie Prefix Tree, but here we can have . characters, which means we just have to go through each child of the current node
- Whenever we reach a . character, we need to exhaust all possible avenues, so we can just have a recursive Depth-first Search function, where we will pass in the current node and the index we're at. If we reach the end of the word, we return True. If not, we return false
- When a dot is reached, we basically search all possible children through DFS and see if they have an end of word
- This is why we have the condition if(dfs..) return True. And then after all children are checked, we return False
- It's kinda hard to explain but if you're having trouble just watch the NeetCode video.
| Time | Space | Explanation |
|---|---|---|
O() | O() |
class TrieNode:
def __init__(self):
self.children = {}
self.end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
cur = self.root
for ch in word:
if ch not in cur.children:
cur.children[ch] = TrieNode()
cur = cur.children[ch]
cur.end = True
def search(self, word: str) -> bool:
def dfs(root, i):
cur = root
for j in range(i, len(word)):
ch = word[j]
if ch == '.':
for child in cur.children.values():
if dfs(child, j + 1):
return True
return False
elif ch not in cur.children:
return False
cur = cur.children[ch]
return cur.end
return dfs(self.root, 0)