Spell Checker with Prefix Suggestions
Filed under Nvidia
Free read 2 of 3Understand dictionary size, character set, and whether suggestions need to be returned in lexicographical order.
The question
Implement a spell checker data structure that checks if a complete word exists, and provides word suggestions given a prefix.
Constraints
- Words consist of lowercase English letters.
- Number of words in dictionary up to 10^5.
- Prefix length can range from 1 to the maximum word length.
Examples
- Input
- dictionary = ["apple", "app", "apricot"], prefix = "ap"
- Output
- ["apple", "app", "apricot"]
- Why
- All three words start with the prefix "ap".
Approach
Understand dictionary size, character set, and whether suggestions need to be returned in lexicographical order.
Store words in a list and iterate through all of them to check prefixes, taking O(N * M) time per query.
Use a Trie data structure where each node stores children pointers and a boolean flag for word completion. Prefix queries navigate to the node and collect all descendants.
Empty dictionary, single-character words, and duplicate insertions.
Solution
O(M) time to insert/search where M is word length; O(N * M) space
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Solution:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
curr = self.root
for ch in word:
if ch not in curr.children:
curr.children[ch] = TrieNode()
curr = curr.children[ch]
curr.is_end = True
def search_prefix(self, prefix: str) -> list:
curr = self.root
for ch in prefix:
if ch not in curr.children:
return []
curr = curr.children[ch]
result = []
self._dfs(curr, list(prefix), result)
return result
def _dfs(self, node, path, result):
if node.is_end:
result.append("".join(path))
for ch, child in sorted(node.children.items()):
path.append(ch)
self._dfs(child, path, result)
path.pop()
Tips
- What they are testing: Test with an empty prefix, a prefix that matches no words, and exact word matches.
- Common mistake: Using a simple hash set for prefix matching, which leads to O(N * M) scans instead of an efficient Trie traversal.
Follow-ups
- How to suggest words starting with a given prefix?
Related Nvidia questions
Collected from public candidate posts and coding forums. Updated Nov 2026.