Edit Distance

Signal

Two strings, three possible operations at every position, and the cost of transforming a pair of prefixes depends on the cost of transforming slightly shorter prefixes — the same "state = (index into A, index into B)" shape as LCS, but the transition now has three choices instead of one comparison.

Approach

Build dp[i][j] = the minimum edits to turn s1[:i] into s2[:j]. If the last characters match, no edit is needed there — inherit dp[i-1][j-1]. If they don't match, take the cheapest of three moves plus one edit: delete from s1 (dp[i-1][j]), insert into s1 (dp[i][j-1]), or replace (dp[i-1][j-1]). The base row and column handle turning a string into/from empty, which costs exactly its length in insertions or deletions.

Skeleton

dp[i][0] = i ; dp[0][j] = j
for i in 1..len(s1):
    for j in 1..len(s2):
        if s1[i-1] == s2[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[len(s1)][len(s2)]

Solution

def min_distance(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    prev = list(range(n + 1))
    for i in range(1, m + 1):
        curr = [i] + [0] * n
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
        prev = curr
    return prev[n]

Complexity

O(m · n) time — one cell per pair of prefixes, constant work each. O(n) space by keeping only the previous row instead of the full 2-D table.

Pitfalls

• Mixing up which move is delete vs insert — dp[i-1][j] means "s1 already matches s2's first j chars using one fewer s1 character," i.e. a deletion from s1; dp[i][j-1] is the insertion. Getting them backwards doesn't change the final number (the problem is symmetric) but will confuse anyone reconstructing the actual edit sequence.
• Forgetting the base row/column (dp[i][0] = i, dp[0][j] = j) — those encode "transform to/from an empty string," and skipping them corrupts every cell that depends on an edge.
• This is easy to mistake for LCS with a different scoring rule — LCS only ever keeps or drops, while edit distance's replace operation lets it fix a mismatch in one step, which is why the recurrences differ by more than just the base case.