Back
+30 XP
Concept

Prefix Tree (Trie) with Fast Autocomplete

Scanning huge word arrays for autocompletion wastes CPU cycles. A Prefix Tree (Trie) organizes words into shared ancestral character paths. Finding all matches starting with `"car"` requires stepping down three edges and traversing child nodes in $O(L)$ time independent of dictionary size 🌲🔍⚡.

python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.end = False

class MiniTrie:
    def __init__(self): self.root = TrieNode()
    def add(self, word):
        curr = self.root
        for c in word: curr = curr.children.setdefault(c, TrieNode())
        curr.end = True

t = MiniTrie()
t.add("api")
print("Trie populated 🚀")

# 17. Prefix Tree (Trie) with Fast Autocomplete When a user types three characters into a search bar, scanning a database table of 500,000 product names using `WHERE name LIKE 'ca%'` causes heavy table scans and unindexed index thrashes 🛑. ```python # The Trie Structural Shared Prefix: # (root) # / \ # 'c' 'd' # | | # 'a' 'o' # / \ | # 'r' 't' 'g'* # / \ \ # * 't'* 'e' # \ # 'r'* # # Words: car, cart, cat, cater, dog ``` ### Sub-Millisecond Typeahead - Navigating to prefix `'ca'` takes exactly 2 pointer hops regardless of whether the dictionary has 10 words or 10,000,000 words. - From node `'ca'`, a lightweight Depth-First Search (DFS) yields all valid terminal descendants in lexicographical order. - Time complexity: **$O(L)$** lookup time 🌲🔍⚡! --- ### Interactive Pop-Quiz 🧠 #### What is the time complexity to search for a word of length $L$ in a Trie containing $N$ total dictionary words? - [ ] $O(L)$ (strictly proportional to the length of the query word, completely independent of the total number of words $N$) ⚡ - [ ] $O(N \times L)$ - [ ] $O(2^N)$ - [ ] $O(1)$ constant time --- ### Practical Challenge 🎯 Implement `Trie` with `insert(word: str)`, `search(word: str) -> bool`, and `autocomplete(prefix: str) -> list[str]`. Insert `['cat', 'cater', 'cart', 'car', 'dog']`. Verify `search('car')` is `True` and `'card'` is `False`. Autocomplete `'ca'` returning sorted matches `['car', 'cart', 'cat', 'cater']`, assert result, and print completions. <details> <summary>Solution</summary> ```python class TrieNode: def __init__(self): self.children = {} self.is_terminal = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str): curr = self.root for ch in word: if ch not in curr.children: curr.children[ch] = TrieNode() curr = curr.children[ch] curr.is_terminal = True def search(self, word: str) -> bool: curr = self.root for ch in word: if ch not in curr.children: return False curr = curr.children[ch] return curr.is_terminal def autocomplete(self, prefix: str) -> list[str]: curr = self.root for ch in prefix: if ch not in curr.children: return [] curr = curr.children[ch] results = [] def _dfs(node: TrieNode, path: list[str]): if node.is_terminal: results.append("".join(path)) for char in sorted(node.children.keys()): _dfs(node.children[char], path + [char]) _dfs(curr, list(prefix)) return results trie = Trie() for w in ["cat", "cater", "cart", "car", "dog"]: trie.insert(w) assert trie.search("car") is True assert trie.search("card") is False completions = trie.autocomplete("ca") assert completions == ["car", "cart", "cat", "cater"] print(f"Trie autocomplete verified: {completions}") ``` </details>

Checkpoint

What is the time complexity to search for a word of length $L$ in a Trie containing $N$ total dictionary words? 🧠

Practice

Implement `Trie` with `insert(word: str)`, `search(word: str) -> bool`, and `autocomplete(prefix: str) -> list[str]`. Insert `['cat', 'cater', 'cart', 'car', 'dog']`. Verify `search('car')` is `True` and `'card'` is `False`. Autocomplete `'ca'` returning sorted matches `['car', 'cart', 'cat', 'cater']`, assert result, and print completions. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks