Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Edit Distance
• Main tags: String, Dynamic Programming

What the problem is really asking

Two strings are given, word1 and word2.

The goal is to transform word1 into word2 using as few operations as possible. The allowed operations are:

• insert one character
• delete one character
• replace one character

This is not a greedy string-matching problem. A locally good edit can make the rest of the string worse, so the real challenge is deciding which prefixes of the two words should be matched together.

Why the naive idea breaks down

A first instinct is recursion:

• if the current characters already match, move both pointers forward
• otherwise try insert, delete, and replace, then take the minimum

That logic is correct, but it repeats the same subproblems many times.

For example, once the algorithm asks for the best answer for the suffixes starting at positions i and j, that same question appears again from multiple recursive branches. Without caching, the runtime grows exponentially.

That is the signal that this is a dynamic programming problem.

The key insight

The cleanest way to think about the problem is by prefixes.

Let dp[i][j] mean:

the minimum number of edits needed to convert the first i characters of word1 into the first j characters of word2.

Once that state is defined, the base cases become natural:

• dp[i][0] = i because deleting all i characters is the only way to reach an empty string
• dp[0][j] = j because inserting all j characters is the only way to build the target from an empty string

Now look at the last characters of those prefixes:

• if word1[i - 1] == word2[j - 1], no new edit is needed, so dp[i][j] = dp[i - 1][j - 1]
• otherwise the last step must be one of three choices:
  • delete from word1: dp[i - 1][j] + 1
  • insert into word1: dp[i][j - 1] + 1
  • replace the last character: dp[i - 1][j - 1] + 1

So the recurrence is:

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

That recurrence works because every valid edit sequence must end in exactly one of those cases.

How to derive the optimal solution in an interview

A practical interview path is:

1. Start with the recursive definition because it matches the problem statement directly.
2. Notice that the recursion keeps asking the same prefix-pair questions again and again.
3. Turn those repeated questions into a memoized cache or a DP table.
4. Observe that each state only depends on the current row, the previous row, and the diagonal value from the previous row.
5. Compress the full table into a rolling row to reduce space.

That progression matters because the rolling-row solution is much easier to remember once it is seen as a space optimization of the full 2D DP.

Best approaches

There are two versions worth knowing.

The full 2D DP table is the easiest to reason about:

• Time: O(m * n)
• Extra space: O(m * n)
• Best use: explaining the recurrence clearly

The rolling-row DP is the best implementation for this problem:

• Time: O(m * n)
• Extra space: O(min(m, n))
• Why it works: each cell depends only on the current row’s left value, the previous row’s same-column value, and the previous row’s diagonal value

For LeetCode 72, the rolling-row version is usually the right final answer.

Python solution

The implementation below uses the rolling-row idea.

It keeps the shorter word as the DP column dimension so memory stays small. For each character in the longer word, it builds one new DP row from left to right.

At each cell, the code compares three possibilities:

• delete the current character from the source prefix
• insert the current target character
• replace the current character if the two characters differ

If the characters already match, the diagonal value carries forward unchanged.

That preserves the exact same recurrence as the full table while using only one previous row at a time.

The result is:

• Time: O(m * n)
• Extra space: O(min(m, n))

Interview follow-ups

Can you reconstruct the actual sequence of edits, not just the count?

Yes. The most straightforward answer is to keep the full O(m * n) DP table, then walk backward from dp[m][n] to dp[0][0]. At each step, compare the current cell with its neighbors to determine whether the optimal path came from a match, insert, delete, or replace decision. This works because the recurrence explicitly encodes the best previous state. The tradeoff is memory: the distance itself only needs a rolling row, but reconstructing the exact edit script usually needs either the full table or extra parent pointers.

What if insert, delete, and replace have different costs?

The same DP structure still works. The only change is that the recurrence adds the appropriate operation-specific weight instead of always adding 1. For example, deletion might cost delete_cost, insertion might cost insert_cost, and replacement might cost replace_cost. The recurrence remains valid because the optimal substructure does not change; only the edge weights do. The complexity stays O(m * n) time, with either O(m * n) space for the full table or O(min(m, n)) space for the rolling-row version.

What if the strings are very large and memory is tight?

The expected answer is the rolling-row optimization used here. Because each DP row depends only on the previous row, the algorithm can discard older rows immediately and keep memory at O(min(m, n)). That is the best default if only the final edit distance is needed. The tradeoff is that reconstructing the exact operations becomes harder. If an interviewer pushes on both low memory and path reconstruction, a stronger answer is to mention divide-and-conquer techniques such as Hirschberg-style reconstruction, which recover an optimal path with linear space but add implementation complexity.

What if the interviewer only cares whether the edit distance is at most k?

Then it is often possible to prune the work. If only a small threshold k matters, the DP only needs to consider states near the main diagonal, because any prefix-pair whose length difference already exceeds k cannot lead to a valid answer within that limit. This gives a banded-DP style solution that can be much faster in practice when k is small relative to the string lengths. The tradeoff is that this is an optimization for a different question. For the original LeetCode problem, the general O(m * n) DP remains the cleanest and most broadly correct approach.

Production-ready Python code

from typing import Tuple


def order_words_by_length(first_word: str, second_word: str) -> Tuple[str, str]:
    """
    Return the words ordered as (longer_or_equal, shorter).

    Edit distance is symmetric when insert, delete, and replace all cost 1,
    so using the shorter word for the DP columns reduces memory.
    """
    if len(first_word) >= len(second_word):
        return first_word, second_word
    return second_word, first_word


def compute_edit_distance(source_word: str, target_word: str) -> int:
    """Compute the Levenshtein edit distance between two strings."""
    longer_word, shorter_word = order_words_by_length(source_word, target_word)

    previous_row = list(range(len(shorter_word) + 1))

    for longer_index, longer_character in enumerate(longer_word, start=1):
        current_row = [longer_index] + [0] * len(shorter_word)

        for shorter_index, shorter_character in enumerate(shorter_word, start=1):
            if longer_character == shorter_character:
                current_row[shorter_index] = previous_row[shorter_index - 1]
                continue

            deletion_cost = previous_row[shorter_index] + 1
            insertion_cost = current_row[shorter_index - 1] + 1
            replacement_cost = previous_row[shorter_index - 1] + 1

            # Choose the cheapest final operation for these two prefixes.
            current_row[shorter_index] = min(
                deletion_cost,
                insertion_cost,
                replacement_cost,
            )

        previous_row = current_row

    return previous_row[-1]


class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        """LeetCode entry point."""
        return compute_edit_distance(source_word=word1, target_word=word2)