Edit Distance

Q: What is the time complexity of Edit Distance?

The table solution runs in O(n × m) time, where n and m are the two lengths, because it fills one cell per pair of prefixes with constant work. It uses O(n × m) memory for the full table, or O(min(n, m)) with two rows. Plain recursion without a table is exponential.

Q: How do you get the list of edits, not only the count?

Keep the full table and walk back from dp[n][m] . If the letters match, step diagonally with no edit. Otherwise step to the neighbor whose value is one less: the diagonal is a replace, up is a delete, left is an insert. Stop at dp[0][0] and read the edits in reverse. The two row version cannot do this on its own, because it has thrown the earlier rows away.

Q: Can Edit Distance be solved with a single array?

Yes. Fill one array row in place, left to right. Before you overwrite row[j] , it still holds the value from the row above, and row[j-1] already holds the current row. The only value you lose is the diagonal, so keep it in a variable: save the old row[j] before writing, and use it as the diagonal for j + 1 .

HardDynamic programming

+10

You get two words, word1 and word2. One edit changes word1 in one of three ways: insert a letter anywhere, delete a letter, or replace a letter with a different one. Return the fewest edits that turn word1 into word2.

Function

minDistance(word1: string, word2: string) → integer

word1string: the word you edit
word2string: the word to reach
Returnsinteger: the fewest inserts, deletes and replaces that turn word1 into word2

Constraints

1 ≤ word1.length ≤ 500
1 ≤ word2.length ≤ 500
Both words contain only lowercase English letters.

Examples

Input: word1 = "spot"word2 = "stop"
Output: 2
Explanation: Replace the p with t and the t with p: spot becomes stot, then stop. One edit is not enough, because the words differ in two places and an insert or a delete would change the length.

Input: word1 = "garden"word2 = "ardent"
Output: 2
Explanation: Delete the g to get arden, then insert t at the end to get ardent. Replacing letter by letter would cost 6, because the two words differ at every position.

Input: word1 = "rain"word2 = "shine"
Output: 3
Explanation: Replace r with s and a with h to get shin, then insert e. Two edits cannot do it: r and a do not appear in shine, so each of them costs an edit that does not make the word longer, and the word still has to grow by one letter.

+21 hidden tests on Submit

Follow-up

Can you also return one shortest list of edits, not only how many there are?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Edits interact, so you cannot fix the words position by position: garden and ardent differ at all six positions, yet two edits are enough once the g is deleted and everything shifts left. The idea that cracks it is to look only at the last letter of each word. Either the two letters already agree, or one of exactly three edits makes them agree, and each choice leaves the same problem on shorter prefixes. A table of (n+1) × (m+1) answers solves every pair of prefixes once, and two rows of it are enough.

Try all three edits with recursion

Correct, but does not finish on the largest tests

Intuition

Let edits(i, j) be the fewest edits that turn the suffix word1[i:] into word2[j:]. Look at the first letters of the two suffixes. If they are equal, keep them and move both indexes on: a matching letter never needs an edit, and any plan that spends an edit on it can be changed into one that keeps it without getting longer.

If they differ, some edit has to deal with word1[i] or produce word2[j], and there are exactly three ways. Replace word1[i] with word2[j], and both indexes move on: edits(i+1, j+1). Delete word1[i], and only i moves: edits(i+1, j). Insert word2[j] in front of it, and only j moves: edits(i, j+1). The answer is 1 plus the cheapest of the three. When word1 runs out, insert the rest of word2, which costs m - j; when word2 runs out, delete the rest of word1, which costs n - i.

It is slow because every mismatch starts three calls. For two words of 15 letters with no letter in common, that is about 6.7 × 10^10 calls, and the large tests have 500 letters each. Yet there are only (n+1) × (m+1) different pairs (i, j), so almost every call repeats one made before.

Algorithm

Write edits(i, j) for the suffixes starting at i and j.
If i is past the end of word1, return m - j; if j is past the end of word2, return n - i.
If word1[i] == word2[j], return edits(i+1, j+1).
Otherwise return 1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)) for replace, delete and insert.
The answer is edits(0, 0).

def minDistance(word1, word2):
    n, m = len(word1), len(word2)

    def edits(i, j):
        # Fewest edits to turn word1[i:] into word2[j:]
        if i == n:
            return m - j  # insert the rest of word2
        if j == m:
            return n - i  # delete the rest of word1
        if word1[i] == word2[j]:
            return edits(i + 1, j + 1)
        return 1 + min(edits(i + 1, j + 1),  # replace word1[i] with word2[j]
                       edits(i + 1, j),      # delete word1[i]
                       edits(i, j + 1))      # insert word2[j]

    return edits(0, 0)

Fill a table of prefixes

Intuition

State. Let dp[i][j] be the fewest edits that turn the first i letters of word1 into the first j letters of word2. Index 0 stands for an empty prefix.

Transitions. Compare the last letters of the two prefixes, word1[i-1] and word2[j-1]. If they are equal, keep them: dp[i][j] = dp[i-1][j-1], the cell diagonally up and left. If not, pay one edit and take the cheapest of three neighbors. The diagonal dp[i-1][j-1] means replace word1[i-1] with word2[j-1]. The cell above, dp[i-1][j], means delete word1[i-1]. The cell to the left, dp[i][j-1], means insert word2[j-1] at the end.

Base row and column. Unlike many table problems, they are not zeros. Turning i letters into an empty prefix takes i deletes, so dp[i][0] = i. Building j letters from nothing takes j inserts, so dp[0][j] = j. Every cell reads the cell above, the one to its left and the diagonal, so filling row by row, left to right, finds them ready. The answer is dp[n][m].

Here is the table for spot into stop, with columns for the prefixes "", s, st, sto, stop. Row "" is [0, 1, 2, 3, 4], row s is [1, 0, 1, 2, 3], row sp is [2, 1, 1, 2, 2], row spo is [3, 2, 2, 1, 2] and row spot is [4, 3, 2, 2, 2]. Read a few cells. s against s matches, so it copies the diagonal 0. sp against st does not: its neighbors are 0 on the diagonal, 1 above and 1 to the left, so it is 1 + 0 = 1, one replace. spo against sto matches on o and copies that 1. The last cell, spot against stop, compares t with p: its neighbors are 1, 2 and 2, so the answer is 1 + 1 = 2.

The table has (n+1) × (m+1) cells with constant work each, about 2.5 × 10^5 steps for two words of 500 letters. A memoized recursion fills the same cells, but it can recurse up to n + m calls deep, which is past Python's default limit of 1000.

Algorithm

Create a table dp of (n+1) × (m+1) cells.
Set dp[i][0] = i for every i and dp[0][j] = j for every j.
For i from 1 to n and j from 1 to m, if word1[i-1] == word2[j-1], set dp[i][j] = dp[i-1][j-1].
Otherwise set dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
Return dp[n][m].

def minDistance(word1, word2):
    n, m = len(word1), len(word2)
    # dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i  # delete all i letters
    for j in range(m + 1):
        dp[0][j] = j  # insert all j letters
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],  # replace
                                   dp[i - 1][j],      # delete word1[i-1]
                                   dp[i][j - 1])      # insert word2[j-1]
    return dp[n][m]

Keep only two rows

Intuition

Row i reads only row i-1 and its own cells to the left. Once a row is finished, the rows above it are never read again. Keep two arrays: prev for the finished row and cur for the row you are filling, and swap them after each row. The transitions do not change: the diagonal is prev[j-1], above is prev[j] and left is cur[j-1].

The base column does not disappear. It now lives in the first entry of each row, so set cur[0] = i before you fill row i. Row 0 starts as [0, 1, 2, ..., m], the base row.

Turning word2 into word1 takes the same number of edits, because every insert becomes a delete and every delete an insert. So you can swap the words and let the rows run along the shorter one. Each row then holds min(n, m) + 1 numbers instead of a table of up to 251,001 cells, and the work stays O(n × m).

Algorithm

If word2 is longer than word1, swap them.
Set prev = [0, 1, ..., m], where m is the shorter length.
For each i from 1 to n, set cur[0] = i, then fill cur[1..m] with the same rule, reading the diagonal and above from prev and the left from cur.
Swap prev and cur.
Return prev[m].

def minDistance(word1, word2):
    if len(word2) > len(word1):
        word1, word2 = word2, word1  # the rows run along the shorter word
    m = len(word2)
    # prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
    prev = list(range(m + 1))
    for i in range(1, len(word1) + 1):
        cur = [i] + [0] * m  # i letters into an empty prefix: delete them all
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j - 1],  # replace
                                 prev[j],      # delete word1[i-1]
                                 cur[j - 1])   # insert word2[j-1]
        prev = cur
    return prev[m]

Pitfalls and edge cases

The recurrence is short, so most bugs are in the base cases or in which neighbor is read.

Filling row 0 and column 0 with zeros, as in longest common subsequence. Turning abc into an empty prefix costs 3 deletes, not 0, so dp[i][0] must be i and dp[0][j] must be j.
Forgetting cur[0] = i in the two row version. The first entry keeps a value from two rows earlier, and every cell after it is off.
Paying an edit on a match. dp[i][j] = 1 + min(...) for equal letters makes a into a cost 1. On a match, copy the diagonal.
Reading the left neighbor from prev instead of cur. Left is the current row: it is the insert of word2[j-1] after word1[:i] is already turned into word2[:j-1].
Comparing position by position. Counting the places where the words differ ignores inserts and deletes: it gives 6 for garden and ardent, while the answer is 2.
Memoizing with recursion on 500-letter words. The call depth reaches 1000, which is Python's default limit.

Frequently asked questions4

What is the time complexity of Edit Distance?

The table solution runs in O(n × m) time, where n and m are the two lengths, because it fills one cell per pair of prefixes with constant work. It uses O(n × m) memory for the full table, or O(min(n, m)) with two rows. Plain recursion without a table is exponential.

Is edit distance the same as Levenshtein distance?

Yes, this version is the Levenshtein distance: insert, delete and replace each cost one. Edit distance is the family name. Other members allow fewer or more edits: only inserts and deletes gives n + m - 2 × LCS, only replaces on equal lengths gives the Hamming distance, and adding a swap of two neighboring letters gives the Damerau version.

How do you get the list of edits, not only the count?

Keep the full table and walk back from dp[n][m]. If the letters match, step diagonally with no edit. Otherwise step to the neighbor whose value is one less: the diagonal is a replace, up is a delete, left is an insert. Stop at dp[0][0] and read the edits in reverse. The two row version cannot do this on its own, because it has thrown the earlier rows away.

Can Edit Distance be solved with a single array?

Yes. Fill one array row in place, left to right. Before you overwrite row[j], it still holds the value from the row above, and row[j-1] already holds the current row. The only value you lose is the diagonal, so keep it in a variable: save the old row[j] before writing, and use it as the diagonal for j + 1.

Python

def minDistance(word1, word2):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

word1 = "spot"
word2 = "stop"

Expected

Edit Distance

Function

Constraints

Examples

Hints

Solution

Try all three edits with recursion

Fill a table of prefixes

Keep only two rows

Pitfalls and edge cases

Frequently asked questions4

Similar problems