Edit Distance – Solution & Complexity

Q: What is the time and space complexity of Edit Distance?

The optimal Edit Distance solution runs in `O(m*n)` time and `O(n)` space. 2D DP over prefixes, taking the min of insert, delete, and replace (compressible to one row).

Q: What is the most efficient way to solve Edit Distance?

2D DP over prefixes, taking the min of insert, delete, and replace (compressible to one row). This gives `O(m*n)` time complexity, and is a classic strings and dynamic programming problem.

Q: How do you solve Edit Distance in Python & JavaScript?

We provide a worked Edit Distance solution in Python & JavaScript with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Edit Distance an easy or hard interview question?

Edit Distance is generally rated **Hard**. It tests strings and dynamic programming, which are common coding-interview patterns.

1. Define the Subproblem

Let dp[i][j] be the minimum edits needed to convert the first i characters of word1 into the first j characters of word2.
Empty prefixes give the base cases: converting to or from an empty string requires only insertions or deletions.
The final answer is the value for the full lengths of both words.

2. Choose Between the Three Operations

If the current characters match, no new edit is needed and we reuse the diagonal subproblem.
Otherwise, try the cheapest of insert, delete, or replace.
Each operation costs one edit plus the best smaller subproblem.

if word1[i - 1] == word2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1]
else:
    dp[i][j] = 1 + min(
        dp[i][j - 1],      # insert
        dp[i - 1][j],      # delete
        dp[i - 1][j - 1],  # replace
    )

3. Optimize Space with One Row

The recurrence only needs the previous row and the current row.
Store distances for converting the processed prefix of word1 to every prefix of word2.
For each character in word1, build a fresh current row from previous.

previous = list(range(len(word2) + 1))
for i in range(1, len(word1) + 1):
    current = [i] + [0] * len(word2)
    # Fill current[j] using previous and current[j - 1].

4. Fill Rows Left to Right

current[j - 1] represents insertion, because the target prefix is one character shorter.
previous[j] represents deletion, because the source prefix is one character shorter.
previous[j - 1] represents replacement or a character match.

for j in range(1, len(word2) + 1):
    if word1[i - 1] == word2[j - 1]:
        current[j] = previous[j - 1]
    else:
        current[j] = 1 + min(current[j - 1], previous[j], previous[j - 1])

5. Final Complete Solution

This dynamic programming solution handles empty strings through the initialized base row and first column.
It keeps only one previous row, so memory is linear in the length of word2.
Time complexity is O(mn), and extra space complexity is O(n).

def min_distance(word1: str, word2: str) -> int:
    previous = list(range(len(word2) + 1))

    for i in range(1, len(word1) + 1):
        current = [i] + [0] * len(word2)
        for j in range(1, len(word2) + 1):
            if word1[i - 1] == word2[j - 1]:
                current[j] = previous[j - 1]
            else:
                current[j] = 1 + min(
                    current[j - 1],
                    previous[j],
                    previous[j - 1],
                )
        previous = current

    return previous[-1]

Edit Distance – Solution & Complexity

1. Define the Subproblem

2. Choose Between the Three Operations

3. Optimize Space with One Row

4. Fill Rows Left to Right

5. Final Complete Solution

FAQ

What is the time and space complexity of Edit Distance?

What is the most efficient way to solve Edit Distance?

How do you solve Edit Distance in Python & JavaScript?

Is Edit Distance an easy or hard interview question?