← Nvidia questions

Spell Checker with Prefix Suggestions

Filed under Nvidia

Free read 2 of 3

Understand 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

  1. Understand dictionary size, character set, and whether suggestions need to be returned in lexicographical order.

Solution

O(M) time to insert/search where M is word length; O(N * M) space

Python
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.