Problem Breakdown
Spell Checker
Published ·
easy
Try This Problem Yourself
Practice in the AI-enabled editor with real-time feedback
You are given a dictionary that maps words to their frequencies, and a query that might be misspelled. Return up to maxSuggestions real words that are within maxDistance edit operations of the query, ranked by edit distance first (fewer edits wins) and frequency second (more common wins among ties).
"Edit distance" here is the Levenshtein distance, which counts the minimum number of single-character insertions, deletions, or substitutions needed to transform one string into another.
query: "helo" → ["help", "hello", "he", "her", "here"]
query: "hourse" → ["house", "horse", "hose"]
query: "thier" → ["the", "this", "they", "her", "there"]Two knobs set the budget. maxDistance defaults to 2, which is the practical upper bound for single-word typos. maxSuggestions caps the result length and defaults to 5.
Tiebreak is worth pausing on. At the same distance, you want to surface the more common word first, because a user's misspelling is much more likely to have targeted a frequent word than a rare one. "teh" should suggest "the" over "he" even though both are within 2 edits.
Pattern: Dynamic Programming
Edit distance is the canonical dynamic programming problem. You fill a table where each cell reuses the answers to smaller subproblems, turning an exponential search into a simple grid of lookups.
Solution 1, scanning everything with full DP
The natural read of the problem is direct. For each candidate word in the dictionary, compute the full edit distance against the query. Keep candidates whose distance is within maxDistance. Sort by (distance ascending, frequency descending). Return the top maxSuggestions words.
Complexity
Where it breaks
Solution 2, rejecting on length before running the DP
Complexity
Where it actually lands
Benchmarks
Takeaways
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium