238. Edit Distance

Why this mechanism works

Use prefix lengths again, but now the state is a minimum transformation cost. Deleting the source's final character comes from above, inserting the target's final character from the left, and replacing from the diagonal. Equal final characters simply inherit the diagonal cost.

State and boundaries

dp[i][j] is the minimum edit cost from source[:i] to target[:j]. Row zero counts insertions; column zero counts deletions.

Protocol

1. Initialize dp[i][0]=i and dp[0][j]=j.
2. Scan positive prefix pairs.
3. Copy the diagonal on equal final characters.
4. Otherwise add one to min(top,left,diagonal).
5. Return the full-prefix cost.

Visualization

horse -> rorse (replace h by r)
rorse -> rose  (delete the extra r)
rose  -> ros   (delete e)
three edits

Python implementation

def edit_distance(source, target):
    m, n = len(source), len(target)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    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 source[i - 1] == target[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 edit_distance: m, n = len(source), len(target)
source='horse'; target='ros'; m=5; n=3

L3 edit_distance: dp = [[0] * (n + 1) for _ in range(m + 1)]
source='horse'; target='ros'; m=5; n=3; _=0

L3 edit_distance: dp = [[0] * (n + 1) for _ in range(m + 1)]
source='horse'; target='ros'; m=5; n=3; _=1

L3 edit_distance: dp = [[0] * (n + 1) for _ in range(m + 1)]
source='horse'; target='ros'; m=5; n=3; _=2

L3 edit_distance: dp = [[0] * (n + 1) for _ in range(m + 1)]
source='horse'; target='ros'; m=5; n=3; _=3

L3 edit_distance: dp = [[0] * (n + 1) for _ in range(m + 1)]
source='horse'; target='ros'; m=5; n=3; _=4

L3 edit_distance: dp = [[0] * (n + 1) for _ in range(m + 1)]
source='horse'; target='ros'; m=5; n=3; _=5

L3 edit_distance: dp = [[0] * (n + 1) for _ in range(m + 1)]
source='horse'; target='ros'; m=5; n=3; dp=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

... 49 intermediate state changes omitted ...

L9 edit_distance: for j in range(1, n + 1):
source='horse'; target='ros'; m=5; n=3; dp=[[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 2, 2], [4, 3, 3, 2], [5, 4, 0, 0]]; i=5; j=2

L13 edit_distance: dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
source='horse'; target='ros'; m=5; n=3; dp=[[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 2, 2], [4, 3, 3, 2], [5, 4, 4, 0]]; i=5; j=2

L9 edit_distance: for j in range(1, n + 1):
source='horse'; target='ros'; m=5; n=3; dp=[[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 2, 2], [4, 3, 3, 2], [5, 4, 4, 0]]; i=5; j=3

L13 edit_distance: dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
source='horse'; target='ros'; m=5; n=3; dp=[[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 2, 2], [4, 3, 3, 2], [5, 4, 4, 3]]; i=5; j=3

L2 edit_distance: m, n = len(source), len(target)
source=''; target='abc'; m=0; n=3

L3 edit_distance: dp = [[0] * (n + 1) for _ in range(m + 1)]
source=''; target='abc'; m=0; n=3; _=0

L3 edit_distance: dp = [[0] * (n + 1) for _ in range(m + 1)]
source=''; target='abc'; m=0; n=3; dp=[[0, 0, 0, 0]]

L4 edit_distance: for i in range(m + 1):
source=''; target='abc'; m=0; n=3; dp=[[0, 0, 0, 0]]; i=0

L6 edit_distance: for j in range(n + 1):
source=''; target='abc'; m=0; n=3; dp=[[0, 0, 0, 0]]; i=0; j=0

L6 edit_distance: for j in range(n + 1):
source=''; target='abc'; m=0; n=3; dp=[[0, 0, 0, 0]]; i=0; j=1

L7 edit_distance: dp[0][j] = j
source=''; target='abc'; m=0; n=3; dp=[[0, 1, 0, 0]]; i=0; j=1

L6 edit_distance: for j in range(n + 1):
source=''; target='abc'; m=0; n=3; dp=[[0, 1, 0, 0]]; i=0; j=2

L7 edit_distance: dp[0][j] = j
source=''; target='abc'; m=0; n=3; dp=[[0, 1, 2, 0]]; i=0; j=2

L6 edit_distance: for j in range(n + 1):
source=''; target='abc'; m=0; n=3; dp=[[0, 1, 2, 0]]; i=0; j=3

L7 edit_distance: dp[0][j] = j
source=''; target='abc'; m=0; n=3; dp=[[0, 1, 2, 3]]; i=0; j=3

Why the solution is correct

The boundaries are the only possible transformations to or from an empty string. For a mismatching final alignment, the last edit is an insertion, deletion or replacement, and each predecessor represents its optimal remaining work. Minimizing those exhaustive alternatives gives the optimal cost; matching endpoints need no final edit.

Time and space

O(m*n) time and O(m*n) auxiliary space for source and target lengths m,n.

Common mistakes

Omitting the empty-prefix row and column makes insertions or deletions at the beginning awkward and error-prone. Treating a swap as one operation computes a different distance.

Reasoning card

Transfer exercise

Assign different insertion, deletion and replacement costs, and revise the boundaries and transition costs explicitly.