Edit distance (Levenshtein) Explained: Tracing 'horse' to 'ros'

Imagine you are building a search engine or spell checker, and a user types horse instead of the intended query ros. If you rely on exact string equality like word1 == word2, your system treats horse and ros as completely unrelated strings with a distance of infinity. Binary equality gives you zero nuance: two words are either identical or entirely different. But in real-world applications, we need to know how different they are, and what minimal set of single-character edits bridges the gap.

To quantify this difference, we turn to the locked working example of transforming word1 = horse into word2 = ros. Without a systematic distance metric, you cannot determine whether horse is closer to ros, house, or moose. We need a principled way to measure the minimum number of character operations required to turn one string into another.

You might be tempted to use simple length differences or shared character counts to measure similarity. However, string horse has length 5 and ros has length 3, a difference of 2, yet simply trimming characters ignores the required replacements and ordering shifts. Counting shared letters also fails because position and sequence matter immensely in human language. We need an algorithmic approach that accounts for insertions, deletions, and substitutions directly on the character stream.

When transforming horse into ros, we are not just making a single all-or-nothing guess; we are making a sequence of localized choices. To capture this systematically, we model the transformation as a two-dimensional grid of subproblems. Imagine a table where the rows correspond to the prefixes of word1 (h, ho, hor, hors, horse) plus an empty string, and the columns correspond to the prefixes of word2 (r, ro, s) plus an empty string.

Each cell at row $i$ and column $j$ in our matrix represents the exact edit distance required to convert the prefix of length $i$ from horse into the prefix of length $j$ from ros. By breaking the giant string-matching problem down into these tiny prefix comparisons, we turn a chaotic search space into a structured path-finding problem.

To move from one cell to the next, our model relies on three fundamental character-level operations:

- Deletion: Remove a character from horse, moving vertically down the grid.
- Insertion: Add a character to match ros, moving horizontally across the grid.

Instead of guessing the optimal sequence of these three operations upfront, our model calculates the cost of all three at every single step and greedily records the minimum. The top-left corner of the grid starts with zero cost for two empty strings, and our ultimate goal is to find the value resting in the bottom-right corner, which corresponds to the full word horse transformed into ros.

To see how dynamic programming solves our target transformation, let us execute the algorithm by hand for word1 = "horse" (rows, length 5) and word2 = "ros" (cols, length 3). We construct a grid $dp$ of size $6\times 4$ (including empty string states at index 0).

Given

- word1 = horse (rows $i=0\dots 5$, where row 0 is empty string "")
- word2 = ros (cols $j=0\dots 3$, where col 0 is empty string "")

Steps

1. Initialize Base Cases: Fill row 0 with values $0,1,2,3$ (representing 0 to 3 insertions needed to form prefixes of ros from an empty ""). Fill column 0 with values $0,1,2,3,4,5$ (representing deletions needed to reduce prefixes of horse to "").
2. Row 1 (h vs "ros"): Compare h against r, o, s.
- At h vs r: characters differ ($1+\min (dp[0][0],dp[1][0],dp[0][1])=1+\min (0,1,1)=1$).
- Continuing across row 1 yields values: [1, 1, 2, 3].
3. Row 2 (o vs "ros"): Compare o. At column 2 (o vs o), characters match! So $dp[2][2]=dp[1][1]=1$. The row becomes [2, 2, 1, 2].
4. Row 3 (r vs "ros"): Compare r. At column 1 (r vs r), characters match ($dp[3][1]=dp[2][0]=2$). Row 3 fills out as [3, 2, 2, 2].
5. Row 4 (s vs "ros"): Compare s. At column 3 (s vs s), characters match ($dp[4][3]=dp[3][2]=2$). Row 4 fills out as [4, 3, 3, 2].
6. Row 5 (e vs "ros"): Compare e against r, o, s. None match.
- For e vs s (bottom-right cell $dp[5][3]$): $1+\min (dp[4][2],dp[5][2],dp[4][3])=1+\min (3,3,2)=3$.

Result

The final bottom-right cell $dp[5][3]$ holds the value 3, which is our minimum edit distance.

Try this: Given the partially filled Levenshtein matrix for word1 = "horse" and word2 = "ros", explain what operation is represented when the algorithm takes the value from the diagonal-left cell ($dp[i-1][j-1]$) instead of computing $1+\min (...)$.

Now that we have traced the full 5-by-3 matrix for transforming horse into ros and arrived at our expected cost of 3, let us test your understanding on a closely related variant using the same exact rules. Instead of the full words, suppose we want to compute the minimum edit distance to transform the prefix hor into the target prefix ro using the same three operations (insert, delete, replace at cost 1).

Recall the core transition rule from our previous steps:

$

Your task is to construct or mentally trace the smaller $3\times 3$ grid for transforming hor (rows, index 0 to 3 including empty string) into ro (columns, index 0 to 2 including empty string) and determine the final value at the bottom-right cell $dp[3][2]$.

Try this: Given word1 = "hor" and word2 = "ro", construct the 2D DP matrix where rows represent prefixes of word1 and columns represent prefixes of word2. What is the final edit distance at the bottom-right cell dp[3][2]?

Now that you have traced the transformation of horse into ros with a cost of 3, you can apply this exact matrix recurrence to broader string-processing pipelines. In real-world spell checkers, you do not just check one target word against one dictionary entry; you compute edit distances across an entire vocabulary to find the minimum-cost matches.

Imagine you are building an autocomplete engine that receives the typo hors and needs to rank candidates from a dictionary containing horse, horsy, hose, and ros. Each candidate requires instantiating a grid of size $(\text{len}(word1)+1)\times (\text{len}(candidate)+1)$ and executing our recurrence relation.

Because computing a full $M\times N$ matrix for every word in a 100,000-word dictionary is computationally heavy, production systems apply optimizations like the Ukkonen's algorithm or length filtering. If the length difference between hors and a dictionary word exceeds your maximum allowed edit distance $k$, you skip the grid calculation entirely.

def get_suggestions(typo, dictionary, max_distance=2):
    suggestions = []
    for word in dictionary:
        if abs(len(typo) - len(word)) <= max_distance:
            if compute_edit_distance(typo, word) <= max_distance:
                suggestions.append(word)
    return suggestions

By establishing our base case bounds and state transitions on small examples like horse and ros, we create a reliable primitive that scales up to fuzzy search, DNA sequence alignment, and natural language translation evaluation.

def rank_closest_word(target, vocabulary):
    # Apply your understanding of edit distance cost matrices
    # to return the word in vocabulary with the minimum distance to target.
    pass