Introduction

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)O(mn) time where mm and nn 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 kk 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 kk. This turns a brute-force scan into something that feels instant.

Try It

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.

<!-- Fuzzy autocomplete demo: trie + Levenshtein edit-distance search -->
<div class="controls">
  <label for="query">Type a word (with typos):</label>
  <input id="query" type="text" placeholder="e.g. algorytm, trie, distanse" autocomplete="off" spellcheck="false" />
  <label for="maxDist">Tolerance (max edits): <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">Suggestions</div>
    <ul id="suggestions"></ul>
    <div id="status" class="status"></div>
  </div>
  <div class="matrix-col">
    <div class="col-title">Distance matrix</div>
    <div id="matrix"></div>
  </div>
</div>

/* base reset and layout */
* { 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; }
/* two-column 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; }
/* suggestion list */
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; }
/* DP matrix table styles */
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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// small curated dictionary of CS terms
const DICT = [
  'algorithm','autocomplete','binary','breadth','circuit','complexity',
  'computer','cycle','data','depth','distance','dynamic','edit',
  'exponential','fibonacci','graph','greedy','hash','heap','heuristic',
  'index','integer','knapsack','levenshtein','linear','logic','matrix',
  'memory','network','node','optimal','path','pattern','polynomial',
  'prefix','prime','programming','pruning','queue','recursion','runtime',
  'search','sequence','sort','stack','string','subset','syntax','trie',
  'vertex'
];

// build a trie from the dictionary
function buildTrie(words) {
  const root = {};
  for (const w of words) {
    let node = root;
    for (const ch of w) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node._ = w;
  }
  return root;
}
const TRIE = buildTrie(DICT);

// compute full Levenshtein DP table for two strings
// Returns the full DP table for two strings (query, word).
function dpTable(query, word) {
  const m = query.length, n = word.length;
  const dp = [];
  for (let i = 0; i <= m; i++) {
    dp[i] = [];
    for (let j = 0; j <= n; j++) {
      if (i === 0) dp[i][j] = j;
      else if (j === 0) dp[i][j] = i;
      else if (query[i - 1] === word[j - 1]) dp[i][j] = dp[i - 1][j - 1];
      else dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
    }
  }
  return dp;
}

// trie fuzzy search with DP-row pruning
// Walk the trie, pruning branches where the DP row minimum exceeds maxDist.
function trieFuzzy(query, maxDist) {
  const results = [];
  const m = query.length;
  // initial DP row = [0,1,2,...,m]
  const initRow = Array.from({ length: m + 1 }, (_, i) => i);

  function dfs(node, ch, row) {
    // extend one DP column for character ch
    const newRow = [row[0] + 1];
    for (let i = 1; i <= m; i++) {
      const cost = query[i - 1] === ch ? 0 : 1;
      newRow[i] = Math.min(newRow[i - 1] + 1, row[i] + 1, row[i - 1] + cost);
    }
    if (newRow[m] <= maxDist && node._) {
      results.push({ word: node._, dist: newRow[m] });
    }
    // prune if no cell in the row is within maxDist
    if (Math.min(...newRow) <= maxDist) {
      for (const c in node) {
        if (c === '_') continue;
        dfs(node[c], c, newRow);
      }
    }
  }

  for (const c in TRIE) {
    dfs(TRIE[c], c, initRow);
  }
  // sort by distance, then alphabetically
  results.sort((a, b) => a.dist - b.dist || a.word.localeCompare(b.word));
  return results;
}

// render the DP table for the top suggestion
function renderMatrix(query, word) {
  if (!query || !word) {
    document.getElementById('matrix').innerHTML = '<p class="placeholder">Type above to see the DP matrix.</p>';
    return;
  }
  const dp = dpTable(query, word);
  const m = query.length, n = word.length;
  // trace back the optimal edit path
  const onPath = new Set();
  let i = m, j = n;
  onPath.add(i + ',' + j);
  while (i > 0 || j > 0) {
    if (i === 0) { j--; }
    else if (j === 0) { i--; }
    else {
      const minVal = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
      if (dp[i - 1][j - 1] === minVal) { i--; j--; }
      else if (dp[i - 1][j] === minVal) { i--; }
      else { j--; }
    }
    onPath.add(i + ',' + j);
  }
  let html = '<table class="dp"><tr><th></th><th></th>';
  for (const ch of word) html += '<th>' + ch + '</th>';
  html += '</tr>';
  for (let r = 0; r <= m; r++) {
    html += '<tr><th>' + (r === 0 ? '' : query[r - 1]) + '</th>';
    for (let c = 0; c <= n; c++) {
      const cls = onPath.has(r + ',' + c) ? 'on-path' : (r === m && c === n ? 'highlight' : '');
      html += '<td' + (cls ? ' class="' + cls + '"' : '') + '>' + dp[r][c] + '</td>';
    }
    html += '</tr>';
  }
  html += '</table>';
  document.getElementById('matrix').innerHTML = html;
}

// render the suggestion list and update the matrix
function renderSuggestions(results, query) {
  const ul = document.getElementById('suggestions');
  const st = document.getElementById('status');
  ul.innerHTML = '';
  if (!query) {
    st.textContent = 'Start typing to see fuzzy suggestions.';
    document.getElementById('matrix').innerHTML = '<p class="placeholder">Type above to see the DP matrix.</p>';
    return;
  }
  if (results.length === 0) {
    st.textContent = 'No matches within this tolerance.';
    document.getElementById('matrix').innerHTML = '<p class="placeholder">Type above to see the DP matrix.</p>';
    return;
  }
  const top = results.slice(0, 6);
  for (const { word, dist } of top) {
    const li = document.createElement('li');
    li.textContent = word;
    const badge = document.createElement('span');
    badge.className = 'badge';
    badge.textContent = i18nFmt('d=%d%', { d: dist });
    li.appendChild(badge);
    ul.appendChild(li);
  }
  st.textContent = i18nFmt('%n% match(es) found.', { n: results.length });
  renderMatrix(query, top[0].word);
}

// wire up input events
function update() {
  const query = document.getElementById('query').value.trim().toLowerCase();
  const maxDist = parseInt(document.getElementById('maxDist').value, 10);
  document.getElementById('distVal').textContent = maxDist;
  const results = trieFuzzy(query, maxDist);
  renderSuggestions(results, query);
}

document.getElementById('query').addEventListener('input', update);
document.getElementById('maxDist').addEventListener('input', update);
update();
Result
Console

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.

The Real Complexity

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)O(mn). The classic DP fills an (m+1)×(n+1)(m+1) \times (n+1) table, where mm = query length and nn = dictionary word length. Each cell takes constant time. For typical autocomplete queries (m≤20m \le 20) and dictionary words (n≤20n \le 20), this is a tiny 400-cell table — trivially fast per word.
  • Naively searching a dictionary of WW words costs O(W⋅mn)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 kk. If the minimum already exceeds kk, the entire subtree is pruned — no word with that prefix can be within distance kk. This cuts the practical cost dramatically when kk is small.
  • Is the DP optimal? For a long time, researchers conjectured that O(mn)O(mn) was tight. In 2015, Backurs and Indyk showed that any algorithm significantly faster than O(n2)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.

Where It Matters

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.

Conclusion

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⋅mn)O(W \cdot mn) brute-force scan into something that keeps up with every keystroke.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/edit-distance-autocomplete/Content licensed under CC BY-NC 4.0.