Trie Essentials
Prompts on the prefix-tree shape, insert and lookup costs, and the autocomplete pattern. Builds the model before tackling KMP-like or word-search problems.
432 views
6
Implement a Trie class with insert(word) and search(word) returning whether the exact word was inserted. Use a dictionary at each node.
Examples
Example 1:
Input: insert('cat'), insert('car'); then search('cat'), search('ca'), search('cars')
Output: True, False, False
Explanation: Each node has a children dict plus an is_end flag. search returns is_end at the destination; 'ca' lands on an internal node so is_end is False, and 'cars' falls off the trie at 's'.class Trie:
def __init__(self):
# TODO
pass
def insert(self, word):
# TODO
pass
def search(self, word):
# TODO
passAdd startsWith(prefix) to the Trie above, returning True iff any inserted word starts with prefix. Justify why this is the trie's natural strength.
Examples
Example 1:
Input: insert('apple'); then starts_with('app'), starts_with('apz')
Output: True, False
Explanation: starts_with walks the trie like search but does NOT require is_end at the destination; reaching the prefix node is enough. 'apz' fails because no edge from the 'p' node matches 'z'.class Trie:
def __init__(self):
self.children = {}
self.is_end = False
def insert(self, word):
node = self
for ch in word:
node = node.children.setdefault(ch, Trie())
node.is_end = True
def starts_with(self, prefix):
# TODO: True iff any inserted word starts with prefix
passGiven the words ["car", "care", "cart", "dog"], sketch the trie shape: list each non-root node by its accumulated prefix and mark which nodes have is_end = True.
Compare a Trie and a HashSet for membership testing on n words of average length m. State time and space complexity, and one scenario where each clearly wins.