Prefix Search and Starts-With
Add a starts_with method that returns true if any inserted word shares a given prefix, and use it to implement autocomplete suggestions.
Prefix Search and Starts-With is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Power of Prefix Queries
The trie's defining advantage over a hash map is efficient prefix querying. A prefix query answers: 'how many stored words start with this prefix?', 'what are all stored words with this prefix?', or simply 'does any word with this prefix exist?'. These queries are O(p) where p is the prefix length, independent of the total number of words stored — making tries ideal for autocomplete and search suggestions.
The starts_with Method
starts_with(prefix) returns True if any stored word begins with the given prefix. Traverse the trie following each character of the prefix. If all characters can be followed without a missing edge, the prefix exists and at least one word starts with it. The implementation is identical to search except we return True as soon as we finish traversing — we don't check is_end.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(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 starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
t = Trie()
for w in ['hello','help','world','word']:
t.insert(w)
print(t.starts_with('hel')) # True
print(t.starts_with('wor')) # True
print(t.starts_with('xyz')) # FalseAutocomplete: Finding All Words with a Prefix
To implement autocomplete, traverse to the prefix's end node, then perform a DFS (or BFS) from that node to collect all words that branch from it. Prepend the prefix to each collected suffix to reconstruct the full words. This is an O(p + W) operation where W is the total number of characters in all matching words.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(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 autocomplete(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return []
node = node.children[c]
# DFS from prefix end node
results = []
def dfs(n, path):
if n.is_end:
results.append(prefix + path)
for char, child in n.children.items():
dfs(child, path + char)
dfs(node, '')
return results
t = Trie()
for w in ['apple','app','application','apply','apt']:
t.insert(w)
print(t.autocomplete('app')) # ['app','apple','apply','application']Returning Sorted Suggestions
For sorted autocomplete, traverse children in alphabetical order during the DFS (iterate over sorted(node.children.items())). Since children are stored in a dict, this adds O(ALPHABET_SIZE × depth) overhead but guarantees lexicographically ordered results. An array-based trie always iterates children in alphabetical order since indices 0-25 are ordered.
def dfs_sorted(node, prefix, results):
if node.is_end:
results.append(prefix)
for char in sorted(node.children.keys()): # alphabetical order
dfs_sorted(node.children[char], prefix + char, results)
print('Iterating children in sorted order gives lex-sorted suggestions')Top-K Autocomplete Suggestions
For top-k suggestions by frequency, augment each node with a count of how many times the word ending there has been searched. When collecting suggestions, use a max-heap of size k. This reduces the O(W) DFS result set to O(k) without materialising all matches. Real-world search engines combine trie prefix traversal with frequency data for fast, relevant suggestions.
Implementing the Trie for LeetCode 208
LeetCode 208 'Implement Trie (Prefix Tree)' asks for exactly: insert(word), search(word) returning exact-match boolean, and startsWith(prefix) returning prefix-match boolean. This is the canonical trie implementation. Remember: search requires is_end=True; startsWith only requires the prefix path to exist.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['#'] = True # '#' marks word end
def search(self, word):
node = self.root
for c in word:
if c not in node: return False
node = node[c]
return '#' in node
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node: return False
node = node[c]
return True
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False
print(t.startsWith('app')) # TrueUsing '#' as End Marker (Dict Trie)
An elegant shortcut stores the trie as nested dicts with a special sentinel key like '#' to mark word endings, eliminating the need for a TrieNode class. This is compact and interview-friendly but slightly less readable than explicit TrieNode objects. Both implementations are acceptable; the dict version is faster to write under time pressure.
Longest Common Prefix Using Trie
To find the longest common prefix of a list of strings, insert all strings into the trie and then traverse from the root, following the single path that exists as long as: (1) the current node has exactly one child, and (2) is_end is False. Stop when either condition breaks. The path followed is the longest common prefix.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def longest_common_prefix(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
prefix = []
node = root
while len(node.children) == 1 and not node.is_end:
char, node = next(iter(node.children.items()))
prefix.append(char)
return ''.join(prefix)
print(longest_common_prefix(['flower','flow','flight'])) # 'fl'
print(longest_common_prefix(['dog','racecar','car'])) # ''Replace Words Problem
Replace Words (LeetCode 648): given a dictionary of root words and a sentence, replace each word in the sentence with the shortest matching root from the dictionary. Insert all roots into a trie. For each word in the sentence, traverse the trie until a root end is found — return that root as the replacement. If no root matches, keep the original word. This runs in O(total chars) vs O(n × m) brute force.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def replaceWords(dictionary, sentence):
root = TrieNode()
for word in dictionary:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def find_root(word):
node = root
for i, c in enumerate(word):
if c not in node.children: break
node = node.children[c]
if node.is_end:
return word[:i+1]
return word
return ' '.join(find_root(w) for w in sentence.split())
print(replaceWords(['cat','bat','rat'], 'the cattle was rattled by the battery'))Map Sum Pairs Problem
Map Sum (LeetCode 677): insert key-value pairs and return the sum of all values whose keys have a given prefix. Augment each TrieNode with a val field. For insert, traverse to the end and set the value; for sum queries, traverse to the prefix end node and DFS-sum all val fields below it. Alternatively, store the cumulative sum in each node during insertion for O(p) queries.
Implementing Autocomplete with Limited Results
In production autocomplete systems, returning all words with a prefix is impractical when thousands of words match. Instead, use a max-heap of size k during the DFS traversal: maintain the k highest-scored words found so far. Stop DFS branches early if they cannot possibly contain a top-k word (pruning by score upper bound). This gives O(p + k × log k) per query for k suggestions — much better than collecting all matches.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: starts_with traverses the prefix path and returns True if it exists — no is_end check needed, autocomplete DFS collects all words from the prefix end node by appending characters as it descends, and augmenting nodes with counts or values enables sum queries and top-k suggestions. Next up we add wildcard and regex matching to the trie.
Frequently asked questions
Is the “Prefix Search and Starts-With” lesson free?
Yes — the full text of “Prefix Search and Starts-With” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Prefix Search and Starts-With”?
Add a starts_with method that returns true if any inserted word shares a given prefix, and use it to implement autocomplete suggestions. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Prefix Search and Starts-With” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- TrieNode Class: Insert and Search
- Prefix Search and Starts-With
- Wildcard and Regex Search in a Trie
- Word Search II: Trie + Backtracking on Grid