Edit Distance

The table is easy to memorize and easy to misuse. The durable idea is simpler: track how far you have consumed each string, then let the final operation determine which earlier states are legal.

The contract and the DP signal

Given word1 and word2, compute the minimum number of single-character operations needed to transform word1 into word2. The permitted operations are:

• Insert one character.
• Delete one character.
• Replace one character.

Both strings may be empty and may have length up to 500. The required result is the minimum operation count, not the sequence of edits.

The solution direction is:

1. Pair every prefix of word1 with every prefix of word2.
2. Define the minimum cost for each prefix pair.
3. Derive transitions from the final operation.
4. Evaluate states in dependency order.

This is a two-dimensional dynamic programming problem because two independent coordinates matter:

• How many characters of word1 have been consumed.
• How many characters of word2 have been produced or matched.

A two-dimensional array by itself is not the reason this is 2D DP. The two meaningful prefix positions are.

Recognition rule: When a problem compares two sequences and progress through both sequences affects the answer, start by inspecting a pair of prefix lengths.

Why greedy and brute force break

A mismatch between two characters does not tell you which operation is optimal.

Suppose the current source character does not match the current target character. Replacing immediately may look natural, but deleting the source character could expose a useful match later. Inserting into the source may also shift the alignment and avoid several replacements.

The problem is alignment. A local decision changes which characters are compared next.

A direct recursive solution makes this visible. For a pair of nonempty prefixes with different final characters, it branches:

• Delete the final source character.
• Insert the final target character.
• Replace the final source character.

Each branch creates smaller prefix problems. But the branches overlap heavily. The same pair of prefix lengths can be reached through different edit orders, so naive recursion recomputes it repeatedly. That branching grows exponentially in the worst case.

Memoization fixes the repeated work by caching each (i, j) state. Bottom-up DP goes one step further: compute the states in an order that guarantees every dependency already exists.

The useful shift is from asking:

“Which edit should I perform first?”

to asking:

“What could the final edit have been?”

The final-operation view gives a small, complete set of predecessors.

Define the two-prefix state

Let:

dp[i][j] = minimum operations needed to convert word1[:i] into word2[:j]

The slices use half-open indexing:

• word1[:i] contains the first i characters of word1.
• word2[:j] contains the first j characters of word2.

If m = len(word1) and n = len(word2), the table has dimensions:

(m + 1) × (n + 1)

The extra row and column represent empty prefixes.

The answer is:

dp[m][n]

This definition is the foundation of the entire implementation. If you change the state meaning halfway through the code, the indexes will look plausible while the recurrence quietly becomes wrong.

Using prefix lengths is safer than using character indexes. Empty strings become ordinary states, and the final characters of the prefixes are simply:

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

Interpret the table as a grid. Moving through the source and target means moving through this grid. Each cell records the cheapest known cost for arriving at one pair of prefix boundaries.

Invariant: After dp[i][j] is computed, it is the optimal cost for exactly word1[:i] to word2[:j], independent of which edit path produced that cost.

Derive the recurrence from the last operation

Consider dp[i][j], where both prefixes are nonempty.

Matching trailing characters

If:

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

the two trailing characters can be aligned without an edit. Remove them from both prefixes:

dp[i][j] = dp[i - 1][j - 1]

There is no reason to replace equal characters under this cost model. A replacement costs one, while keeping the match costs zero.

Mismatching trailing characters

If the trailing characters differ, classify the final operation.

Delete from word1

Delete word1[i - 1]. The remaining problem converts word1[:i - 1] into word2[:j]:

dp[i - 1][j] + 1

The row decreases because one source character has been consumed by deletion. The target prefix remains the same.

Insert into word1

Insert word2[j - 1] into the source. Before that insertion, the remaining problem converts word1[:i] into word2[:j - 1]:

dp[i][j - 1] + 1

The source prefix length stays at i; the target obligation decreases by one.

Replace the final source character

Replace word1[i - 1] with word2[j - 1]. Both trailing characters are handled, leaving:

dp[i - 1][j - 1] + 1

Take the cheapest legal predecessor:

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

The direction matters. A frequent interview bug is to call dp[i][j - 1] a deletion or dp[i - 1][j] an insertion without checking which prefix obligation actually shrank. Name the operation from the transformation semantics, not from the visual direction alone.

Base cases and dependency geometry

The empty-prefix boundaries are forced by the state definition.

To convert a source prefix into an empty target:

dp[i][0] = i

Every source character must be deleted.

To convert an empty source into a target prefix:

dp[0][j] = j

Every target character must be inserted.

The origin is:

dp[0][0] = 0

No work is required to convert an empty string into an empty string.

For an interior cell, the recurrence reads:

• The cell above: dp[i - 1][j]
• The cell to the left: dp[i][j - 1]
• The diagonal cell: dp[i - 1][j - 1]

Therefore, row-major order works. When computing row i from left to right, the previous row is complete, and the current row's left neighbor has already been computed.

For word1 = "ab" and word2 = "ac", the table is:

The bottom-right value is 1: the trailing b can be replaced with c. The match at (1, 1) copies the diagonal zero rather than adding a cost.

Why the recurrence is correct

A compact induction proof is enough.

Assume every state with a smaller total prefix length is correct. The boundary states are correct because converting to or from an empty string has only one possible operation type: delete all source characters or insert all target characters.

Now consider an interior state dp[i][j].

If the trailing characters match, an optimal transformation can align them without cost. Any unnecessary edit to equal characters adds cost and cannot improve the result. The remaining work is exactly dp[i - 1][j - 1], which is correct by the induction assumption.

If the trailing characters differ, every valid transformation has some final operation affecting the end of the target alignment. That final operation must be one of:

1. Delete the final source character.
2. Insert the final target character.
3. Replace one final character with the other.

Removing that final operation leaves exactly one of the three predecessor subproblems. Each predecessor is optimal by induction, and each final operation costs one. Taking the minimum considers every possible final-operation class, so it includes the cheapest valid transformation.

That establishes optimal substructure: an optimal solution is composed of an optimal solution to one smaller prefix pair plus the cost of its final operation.

The proof also explains the fill order. Every predecessor has a smaller i + j than the current cell, so bottom-up evaluation reaches it first.

Dry-run: transforming horse into ros

The standard transformation has distance 3. One valid sequence is:

horse -> rorse   # replace h with r
rorse -> rose    # delete r
rose  -> ros     # delete e

The complete table is:

Focus on the final cell, dp[5][3]. The trailing characters are e and s, so they mismatch:

• Delete e: dp[4][3] + 1 = 2 + 1 = 3
• Insert s: dp[5][2] + 1 = 4 + 1 = 5
• Replace e with s: dp[4][2] + 1 = 4 + 1 = 5

The minimum is 3.

The table stores costs, not the edit script. If the problem asked you to output the operations, you would need to retain predecessor choices or walk backward through the full table after computing the distance. That is a different output contract.

Direction also matters. This table means “convert word1 into word2.” Under the standard unit-cost insert/delete/replace model, swapping the strings produces the same distance value, but the operation labels and transformation direction still change. Keep the state definition explicit rather than relying on symmetry.

Full Python implementation

Start with the full table. It mirrors the proof, makes boundary errors visible, and preserves enough information for debugging.

def min_distance(word1: str, word2: str) -> int:
    m = len(word1)
    n = len(word2)

    # dp[i][j] converts word1[:i] into word2[:j].
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Convert a nonempty source prefix to an empty target: delete.
    for i in range(1, m + 1):
        dp[i][0] = i

    # Convert an empty source to a nonempty target: insert.
    for j in range(1, 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_cost = dp[i - 1][j] + 1
                insert_cost = dp[i][j - 1] + 1
                replace_cost = dp[i - 1][j - 1] + 1

                dp[i][j] = min(
                    delete_cost,
                    insert_cost,
                    replace_cost,
                )

    return dp[m][n]

The code is intentionally plain. Each variable maps directly to a legal final operation, and each index maps directly to a prefix length. That makes the implementation easier to explain under interview pressure and easier to inspect when a test fails.

Compress space by preserving dependencies

The full table uses O(mn) space. But each cell only needs:

• The previous row's value above.
• The current row's value to the left.
• The previous row's diagonal value.

A single list can represent the current row while old values are replaced from left to right.

The dangerous value is the diagonal. Before updating dp[j], its old value is dp[i - 1][j], the cell above. The old diagonal dp[i - 1][j - 1] has already been overwritten during the previous iteration, so preserve it in a temporary variable.

Here is the compressed implementation:

def min_distance_optimized(word1: str, word2: str) -> int:
    # Keep the retained row as short as possible.
    if len(word2) > len(word1):
        word1, word2 = word2, word1

    m = len(word1)
    n = len(word2)

    # Before processing a row, dp[j] represents
    # the previous row's conversion cost.
    dp = list(range(n + 1))

    for i in range(1, m + 1):
        # dp[0] is converting word1[:i] to an empty string.
        dp[0] = i

        # old_diagonal is dp[i - 1][j - 1].
        old_diagonal = i - 1

        for j in range(1, n + 1):
            above = dp[j]  # old dp[i - 1][j]

            if word1[i - 1] == word2[j - 1]:
                dp[j] = old_diagonal
            else:
                dp[j] = min(
                    above + 1,       # delete
                    dp[j - 1] + 1,   # insert; current row's left value
                    old_diagonal + 1 # replace
                )

            old_diagonal = above

    return dp[n]

The invariant is precise:

• Before processing j, dp[j] is the previous row's value.
• dp[j - 1] is the current row's left value.
• old_diagonal is the previous row's diagonal value.
• After the update, dp[j] becomes the current row's value.

This is an in-place dependency audit. Space compression is safe only when every value needed by the recurrence survives until its last use.

Swapping the strings before computation reduces the retained dimension to the shorter string, giving O(min(m, n)) auxiliary space. The distance value remains valid under the standard operation costs. If you later extend the problem to asymmetric operation costs or directional output, re-check that swap against the new contract instead of treating it as automatically safe.

For debugging, I would implement the full table first. The compressed version is a refinement, not the place to discover what the state means.

Complexity, edge cases, and the final check

Let:

m = len(word1)
n = len(word2)

The bottom-up algorithm computes one state for every pair (i, j). Each state performs constant work, so the time complexity is:

O(mn)

Space depends on the representation:

• Full table: O(mn)
• One-row compression: O(n)
• With deliberate orientation: O(min(m, n))

The input limits of 500 make straightforward quadratic DP appropriate for this contract. There is no reason to hide the recurrence behind a more complicated structure.

Test these cases deliberately:

The common implementation failures are predictable:

• Reading word1[i] instead of word1[i - 1].
• Reversing the meaning of insertion and deletion neighbors.
• Adding one even when trailing characters match.
• Forgetting to initialize the first row or first column.
• Updating the compressed row before preserving the old diagonal.
• Returning dp[m - 1][n - 1] instead of the state for the full prefixes.
• Swapping strings in a version whose output contract requires a particular edit direction.

The transferable move is the important part. When a result depends on progress through two sequences, define the paired-prefix state first. Then classify the legal final operations and map each one to the predecessor it leaves behind.

Paired progress gives you the coordinates. Final operations give you the recurrence. Dependency geometry tells you the fill order—and, later, exactly which values can be safely compressed.