72. Edit Distance

Problem¶

Given two strings, return the minimum number of single-character insertions, deletions, or replacements needed to transform the first into the second.

Input:  word1 = "horse", word2 = "ros"
Output: 3
State:  "horse" -> "rorse" -> "rose" -> "ros"

Key trick¶

Use dynamic programming on prefixes: the answer for two prefixes depends only on deleting, inserting, or replacing their final characters.

Trap¶

• Character frequencies are insufficient because edit distance depends on order.
• Greedy matching can miss a better sequence of later edits.
• Empty prefixes require initialization with their lengths.
• A matching pair of characters adds no cost.

Why is it interesting?¶

It turns an exponential choice process into a compact prefix DP and is a standard model for sequence alignment, spell checking, and diff tools.

Python solution¶

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # Keep the DP row proportional to the shorter string.
        if len(word1) < len(word2):
            word1, word2 = word2, word1

        n = len(word2)

        # prev[j] is the distance from the processed prefix of word1
        # to word2[:j].
        prev = list(range(n + 1))

        for i, ch1 in enumerate(word1, 1):
            cur = [i] + [0] * n

            for j, ch2 in enumerate(word2, 1):
                if ch1 == ch2:
                    cur[j] = prev[j - 1]
                else:
                    cur[j] = 1 + min(
                        prev[j],      # Delete ch1.
                        cur[j - 1],   # Insert ch2.
                        prev[j - 1],  # Replace ch1 with ch2.
                    )

            prev = cur

        return prev[n]

• Time complexity: \(O(mn)\)
• Space complexity: \(O(\min(m,n))\)

Comment on my solution¶

• Correctly rejects plain DFS because exploring all edit sequences is exponential.
• Correctly notices that order matters.
• Frequency intersection cannot determine edit distance because it loses character positions and does not model replacement costs.
• The implementation is incomplete; the prefix grid in the notes is the right starting point for dynamic programming.

# Ideas:
# - DFS backtracking is exponential so not appropriate here
# - maybe use intersection of frequency letters to know
#   the letters that must be kept
# - order is important
#    r o s    e x e c u t i o n
#  h        i
#  o        n
#  r        t
#  s        e
#  e        n
#           t
#           i
#           o
#           n


class Solution:
    def minDistance(self, word1: str, word2: str) -> int:

Extra¶

Compelement on DP on prefixes¶

The missing idea is that we do not try to choose the edits directly. Instead, we solve every smaller version of the problem and build the final answer from them.

What does "DP on prefixes" mean?¶

A prefix is the first part of a string.

For "horse":

• Length 0: ""
• Length 1: "h"
• Length 2: "ho"
• Length 3: "hor"
• Length 4: "hors"
• Length 5: "horse"

Define:

For example:

dp[2][2] = distance from "ho" to "ro" = 1

We only need one replacement:

"ho" -> "ro"

The answer to the original problem is therefore:

dp[len(word1)][len(word2)]

How do we compute one cell?¶

Suppose we want to transform:

word1[:i] into word2[:j]

Look at the final characters:

word1[i - 1] and word2[j - 1]

If the final characters match¶

No edit is needed for those characters.

"hor" -> "r"
   r       r

The final r already matches, so we only need to transform the parts before it:

If the final characters differ¶

The final operation must be one of the three allowed operations.

Delete¶

Delete the final character from the first prefix:

"horse" -> "hors"

After deleting it, we still need to transform word1[:i-1] into word2[:j].

Insert¶

Insert the final character needed by the second prefix:

"ro" -> "ros"

Before inserting s, we must transform word1[:i] into word2[:j-1].

Replace¶

Replace the final character of the first prefix with the final character of the second prefix:

"cat" -> "car"

Before that replacement, the preceding prefixes must already match.

Choose the cheapest possibility:

Why do we need the first row and column?¶

Transforming an empty string into a string of length j requires j insertions:

"" -> "r" -> "ro" -> "ros"

Therefore:

Transforming a string of length i into an empty string requires i deletions:

Complete table for "horse" and "ros"¶

Rows are prefixes of "horse". Columns are prefixes of "ros".

         ""  r  o  s
    ""    0  1  2  3
    h     1  1  2  3
    ho    2  2  1  2
    hor   3  2  2  2
    hors  4  3  3  2
    horse 5  4  4  3

The bottom-right value is 3, so the edit distance is 3.

Every cell uses already-computed neighboring cells:

diagonal: replace or match
up:       delete
left:     insert

Visually:

dp[i-1][j-1]    dp[i-1][j]
         |              |
  dp[i][j-1]  --  dp[i][j]

Clear implementation using the full table¶

This version is easier to understand than the space-optimized version:

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)

        # dp[i][j] is the edit distance between
        # word1[:i] and word2[:j].
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # Turning word1[:i] into "" requires i deletions.
        for i in range(m + 1):
            dp[i][0] = i

        # Turning "" into word2[:j] requires j insertions.
        for j in range(n + 1):
            dp[0][j] = j

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    delete = dp[i - 1][j]
                    insert = dp[i][j - 1]
                    replace = dp[i - 1][j - 1]

                    dp[i][j] = 1 + min(delete, insert, replace)

        return dp[m][n]

• Time complexity: \(O(mn)\)
• Space complexity: \(O(mn)\)

The previous solution stores only the current and previous rows because a cell never uses rows older than i - 1. That changes memory usage, but not the underlying idea.

How to recognize DP on prefixes¶

It is a strong candidate when:

• The problem involves one or two sequences, such as strings or arrays.
• You are asked for a minimum, maximum, count, or possibility.
• A solution for the whole sequence can be expressed using solutions for shorter prefixes.
• The final choice involves the final elements of those prefixes.
• A recursive solution would repeatedly solve the same smaller inputs.

A useful question is:

If I know how to solve the problem for shorter prefixes, can I decide what happens with the final character?

For edit distance, the answer is yes:

• Matching final characters can be kept.
• Otherwise, the final operation is an insertion, deletion, or replacement.

That observation gives both the DP state and its recurrence.

A practical recipe for prefix DP¶

• Define what dp[i][j] means in one precise sentence.
• Determine the empty-prefix cases.
• Examine the final elements of the prefixes.
• List every possible final decision.
• Express each decision using a smaller DP state.
• Take the minimum, maximum, sum, or logical combination required.
• Return the state representing the complete inputs.

The most important step is the state definition:

Once that meaning is fixed, the recurrence becomes much easier to derive.