Fuzzy Search (Edit Distance)

For typo tolerance ("did you mean..."), search for words within edit distance K.

Naive: for each word in trie, compute Levenshtein distance to query. O(N * |q| * |w|) — slow for big dictionaries.

Trie-based: walk the trie with a DP table for edit distance:

For each child c of current node:
    new_row = [prev_row[0] + 1]   # insertion
    for i in 1..len(query):
        cost = 0 if query[i-1] == c else 1
        new_row[i] = min(
            new_row[i-1] + 1,        # deletion
            prev_row[i] + 1,         # insertion
            prev_row[i-1] + cost     # substitution
        )
    if min(new_row) > K: prune subtree
    if child.is_word and new_row[-1] <= K: emit
    recurse with new_row

Pruning when minimum row value exceeds K is the key optimization. For a 100k-word dictionary and K=2, this is sub-millisecond.

Used by aspell, fuzzy matchers in code editors, search-suggestion services. Lucene's FuzzyQuery uses similar trie+DP.