Frontend System Design · Lesson 75 of 86 · 4 min
Full-Text Search: Levenshtein and Fuzzy Matching
Knowing this lets you answer "design a typeahead" with specifics, not just hand-waving about "fuzzy search."
When a user types "iPhon" into a search bar, they expect to see "iPhone". Fuzzy matching makes this happen. Your job in an interview is to explain how you'd build it, what the performance costs are, and when to stop doing it on the client.
The core algorithm for this is usually Levenshtein distance.
How Levenshtein distance works
Levenshtein distance measures the difference between two strings. It's the minimum number of single-character edits (insertions, deletions, or substitutions) needed to change one string into the other.
"kitten" to "sitting" has a distance of 3:
- kitten → sitten (substitute 's' for 'k')
- sitten → sittin (substitute 'i' for 'e')
- sittin → sitting (insert 'g')
The standard way to calculate this is with dynamic programming, building a matrix of (s1.length + 1) x (s2.length + 1). The time and space complexity is O(m*n), where m and n are the lengths of the two strings.
This is fine for comparing two short strings. It is not fine for comparing a search query against a 10,000-item product list on every keystroke. That's the central trade-off.
Implementing a basic fuzzy search
You might be asked to code Levenshtein distance from scratch. It's a classic dynamic programming problem. The real goal is to see if you can then apply it.
Here’s a practical implementation that calculates the distance and then uses it to find suggestions from a list.
function levenshteinDistance(s1: string, s2: string): number {
const m = s1.length;
const n = s2.length;
const dp = Array(n + 1).fill(null);
for (let j = 0; j <= n; j++) {
dp[j] = j;
}
for (let i = 1; i <= m; i++) {
let prev = dp[0];
dp[0] = i;
for (let j = 1; j <= n; j++) {
const temp = dp[j];
const cost = s1[i - 1] === s2[j - 1] ? 0 : 1;
dp[j] = Math.min(
dp[j] + 1, // Deletion
dp[j - 1] + 1, // Insertion
prev + cost // Substitution
);
prev = temp;
}
}
return dp[n];
}
function getFuzzySuggestions(
query: string,
dictionary: string[],
maxDistance: number = 2
): string[] {
const suggestions: { word: string; distance: number }[] = [];
const lowerCaseQuery = query.toLowerCase();
for (const word of dictionary) {
const distance = levenshteinDistance(lowerCaseQuery, word.toLowerCase());
if (distance <= maxDistance) {
suggestions.push({ word, distance });
}
}
suggestions.sort((a, b) => a.distance - b.distance);
return suggestions.map(s => s.word);
}
Note: The code above uses a space-optimized version of the DP algorithm (O(n) space instead of O(m*n)) by only keeping track of the previous row. This is a good optimization to mention if you're asked about complexity.
Knowing when to use a library (and why)
Implementing Levenshtein is a good exercise, but for a real app, you'd use a library.
The trap: Suggesting you'd run the function above over a large array on every keystroke. This will block the main thread and create a janky UI. For a 20-character query against 5,000 product names of average length 30, you're looking at millions of operations. This won't fit within a 16ms frame budget.
Libraries like Fuse.js are built for this. They don't just run Levenshtein in a loop. They pre-process the dataset to build an index, often using techniques like n-grams, to quickly narrow down the list of potential matches before running more expensive distance calculations.
This pre-computation is key. The initial indexing takes time, but subsequent searches are fast. This is the trade-off you make.
In an interview, your answer should be: "For a small, fixed list—say, under 500 items—a naive Levenshtein loop inside a debounced event handler might be acceptable. For anything larger, I'd use a dedicated library like Fuse.js to pre-build an index in memory, or I'd offload search to the backend."
Deciding between client-side and server-side search
This is a classic system design question that applies directly to fuzzy search.
Keep it on the client when:
- The dataset is small and relatively static (e.g., country list, command palette options, a few hundred products).
- You need instant, zero-latency feedback as the user types.
- The search needs to work offline.
Move it to the server when:
- The dataset is large (thousands to millions of items).
- The data changes frequently.
- The search logic is complex or needs to weigh results by other factors (e.g., popularity, user history, inventory).
- You need to keep the client bundle size small.
For server-side, you wouldn't implement this yourself. You'd use a dedicated search engine like Elasticsearch or Algolia. They provide fuzzy matching capabilities out of the box, built on highly optimized data structures like inverted indexes.
Other fuzzy matching algorithms to know
Levenshtein is the most famous, but it's not the only one. Knowing the names of others shows you have a broader understanding.
- N-grams: Breaks strings into chunks of N characters. "apple" as 3-grams (trigrams) is "app", "ppl", "ple". You find matches by comparing the set of n-grams between two strings. It's good for finding substring matches and is often used for indexing.
- Phonetic Algorithms (Soundex, Metaphone): Index words by how they sound. Useful for matching names that are spelled differently but sound similar (e.g., "Smith" and "Smyth"). Less common for general-purpose frontend search, but good to be aware of.
You don't need to implement these. Just know what they're for: solving different kinds of "fuzziness" that Levenshtein might miss, like word order or phonetic similarity.
Try it
Take the getFuzzySuggestions function. Refactor it into a React hook, useFuzzySearch(query, list, { maxDistance: 2 }). Add debouncing to the query input so the calculation doesn't run on every single keystroke. Test it with a list of 100 city names.
Next: We'll discuss how to handle larger datasets on the client by creating your own search index in the browser in "Indexing Large Datasets in the Browser".
Lock it in — apply this lesson under interview conditions.