Fuzzy Autocomplete

Type "teh" into a search box and it still finds "the." Mistype "pyton" and the IDE still suggests "python." Behind these everyday miracles sits a single idea: edit distance.

The Levenshtein distance between two strings is the minimum number of single-character insertions, deletions, and substitutions needed to transform one into the other. "kitten" → "sitting" takes three such operations (substitute k→s, substitute e→i, insert g), so their edit distance is 3. Two identical strings have distance 0; every character difference adds at least 1.

Computing that distance for a single pair is solved — Vladimir Levenshtein worked out the dynamic-programming recurrence in 1965 — and the result runs in $O(mn)$ time where $m$ and $n$ are the string lengths. That is cheap enough to run thousands of times per keystroke on the dictionary of a typical autocomplete engine.

The real engineering question is: given a user's (possibly misspelled) prefix, how do you efficiently find all dictionary words within edit distance $k$ without comparing the query to every entry? The answer is to walk a trie — a prefix tree — while carrying the DP matrix forward one column at a time, pruning branches the moment their distance already exceeds $k$. This turns a brute-force scan into something that feels instant.

Type any prefix below — with or without typos — and the demo searches a small dictionary using a trie with edit-distance pruning. Results are ranked by distance from your query, so the closest match always appears first.

<!-- {{c_intro}} -->
<div class="controls">
  <label for="query">{{label_query}}</label>
  <input id="query" type="text" placeholder="{{placeholder_query}}" autocomplete="off" spellcheck="false" />
  <label for="maxDist">{{label_tolerance}} <span id="distVal">2</span></label>
  <input id="maxDist" type="range" min="0" max="4" value="2" />
</div>
<div class="results-row">
  <div class="suggestions-col">
    <div class="col-title">{{title_suggestions}}</div>
    <ul id="suggestions"></ul>
    <div id="status" class="status"></div>
  </div>
  <div class="matrix-col">
    <div class="col-title">{{title_matrix}}</div>
    <div id="matrix"></div>
  </div>
</div>

/* {{c_reset}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .8rem; }
label { font-size: .85rem; color: #555; }
input[type="text"] { font: 1rem system-ui, sans-serif; padding: .4rem .6rem; border: 1px solid #c0c8d0; border-radius: 8px; width: 100%; }
input[type="range"] { width: 100%; accent-color: #1d3557; }
/* {{c_layout}} */
.results-row { display: flex; gap: 1rem; flex-wrap: wrap; }
.suggestions-col { flex: 1 1 140px; }
.matrix-col { flex: 2 1 200px; overflow-x: auto; }
.col-title { font-size: .8rem; font-weight: 700; color: #1d3557; text-transform: uppercase; letter-spacing: .05em; margin-bottom: .4rem; }
/* {{c_suggestions}} */
ul#suggestions { list-style: none; margin: 0; padding: 0; }
ul#suggestions li { padding: .3rem .5rem; border-radius: 6px; margin-bottom: .25rem; font-size: .95rem; display: flex; justify-content: space-between; align-items: center; }
ul#suggestions li:first-child { background: #e0eaf4; font-weight: 700; }
ul#suggestions li .badge { font-size: .75rem; background: #1d3557; color: #fff; border-radius: 12px; padding: .1rem .45rem; margin-left: .4rem; }
ul#suggestions li:first-child .badge { background: #0a7d33; }
.status { font-size: .88rem; color: #888; margin-top: .4rem; min-height: 1.2em; }
/* {{c_matrix_style}} */
table.dp { border-collapse: collapse; font-size: .78rem; font-family: ui-monospace, monospace; }
table.dp th, table.dp td { border: 1px solid #dde4eb; padding: .22rem .4rem; text-align: center; min-width: 26px; }
table.dp th { background: #f0f4f8; font-weight: 700; color: #1d3557; }
table.dp td.highlight { background: #e0eaf4; font-weight: 700; }
table.dp td.on-path { background: #c8f5da; }
.placeholder { color: #aaa; font-size: .9rem; padding: .5rem 0; }

// Code not found

Notice that an exact prefix match (distance 0) always comes first, while typos of one or two characters still surface the right word. Increase the tolerance slider to allow sloppier matches — you'll see more candidates appear, ranked from best to worst. The distance matrix panel shows the classic DP table for the top suggestion, updated live as you type.

Edit distance is one of the problems where complexity theory gives a fully satisfying answer — and a subtler one underneath.

• Exact computation is $O(mn)$. The classic DP fills an $(m+1) \times (n+1)$ table, where $m$ = query length and $n$ = dictionary word length. Each cell takes constant time. For typical autocomplete queries ($m \le 20$) and dictionary words ($n \le 20$), this is a tiny 400-cell table — trivially fast per word.
• Naively searching a dictionary of $W$ words costs $O(W \cdot mn)$, which can be tens of millions of operations per keystroke on a large dictionary. That is why tries matter.
• Trie search with pruning carries a partial DP row as you descend the trie. At each trie node you extend one column of the DP and compare the row's minimum to the threshold $k$. If the minimum already exceeds $k$, the entire subtree is pruned — no word with that prefix can be within distance $k$. This cuts the practical cost dramatically when $k$ is small.
• Is the DP optimal? For a long time, researchers conjectured that $O(mn)$ was tight. In 2015, Backurs and Indyk showed that any algorithm significantly faster than $O(n^2)$ would refute the Strong Exponential Time Hypothesis (SETH) — meaning a truly sub-quadratic algorithm is probably impossible under standard complexity assumptions. So the classic DP is essentially the best we can do.

The takeaway: edit distance lives in the comfortable zone of polynomial-time solvable problems, well below NP-completeness. But its fine-grained complexity — the cost of shaving off a polynomial factor — connects to the deepest open questions in algorithm lower bounds.

Edit distance is one of the most quietly ubiquitous algorithms in computing:

• Spell checking and autocomplete: every major keyboard, search engine, and IDE uses a variant of Levenshtein distance to rank candidates and tolerate typos.
• DNA and protein sequence alignment: bioinformatics tools like BLAST are built on edit-distance-style dynamic programming. The sequence alignment problem that underlies genome assembly is a direct generalization.
• Version control diffs: git diff computes the shortest edit script between two files — a line-level edit distance — to show exactly what changed.
• Plagiarism detection: approximate string matching flags passages that are close but not identical.
• OCR post-correction: when an optical character reader misreads a character, a spell checker finds the closest real word by edit distance.
• Natural language processing: edit distance features appear in named-entity recognition, duplicate detection, and translation quality metrics like TER (Translation Edit Rate).

Whenever two sequences need to be compared for similarity rather than equality, edit distance is usually the right first tool.

Levenshtein's 1965 recurrence is sixty years old and still drives the suggestion box on your phone. The reason is elegant: it defines distance as the minimum cost to transform one string into another, and dynamic programming computes that minimum without ever revisiting a subproblem.

Paired with a trie, it becomes an efficient search: you descend the prefix tree, pruning branches that are already too far from the query, and collect only the candidates worth ranking. The result is an autocomplete that feels forgiving because it is forgiving — not by guessing, but by measuring.

The deeper lesson is about the value of the right metric. Once you can measure closeness precisely, ranking, pruning, and thresholding all follow naturally. Edit distance is the metric; the trie is the index; and together they turn a $O(W \cdot mn)$ brute-force scan into something that keeps up with every keystroke.