Edit Distance

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. Only the diagonal is lost, so save the old row[j] in a variable 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, then insert e. Two edits fail: r and a are not in shine, so each needs an edit that keeps the length, and the word must still grow by one.

Follow-up

Can you also return one shortest list of edits, besides their count?

Hints

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

0 of 3 opened

Solution

Edits interact: garden and ardent differ at all six positions, yet two edits are enough. So look at the last letter of each word. Either the two agree, or one of three edits makes them agree, and each choice leaves the same problem on shorter prefixes. A table solves every pair of prefixes once.

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:]. If the first letters match, keep them and move both indexes: spending an edit on a matching letter never helps. Otherwise take 1 plus the cheapest of three calls: a replace moves both indexes, a delete of word1[i] moves i, and an insert of word2[j] moves j. When one word runs out, each letter left in the other costs one edit.

Every mismatch starts three calls: two 15-letter words with no letter in common take about 6.7 × 10^10 calls. Yet there are only (n+1) × (m+1) different pairs (i, j), so almost every call repeats an earlier one.

Algorithm

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)).
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

Let dp[i][j] be the fewest edits that turn the first i letters of word1 into the first j letters of word2. If word1[i-1] equals word2[j-1], copy the diagonal dp[i-1][j-1]. Otherwise pay 1 plus the cheapest neighbor: the diagonal is a replace, the cell above a delete of word1[i-1], the cell to the left an insert of word2[j-1]. The base row and column are not zeros: i letters into nothing take i deletes, so dp[i][0] = i, and likewise dp[0][j] = j.

For spot into stop the last row is [4, 3, 2, 2, 2]. The final cell compares t with p; its diagonal (spo into sto) is 1 and its other neighbors are 2, so the answer is 1 + 1 = 2. Two 500-letter words fill 2.5 × 10^5 cells, each in constant time.

Algorithm

Create dp with (n+1) × (m+1) cells, dp[i][0] = i and dp[0][j] = 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, so two arrays are enough: prev for the finished row and cur for the row you are filling. The diagonal is prev[j-1], above is prev[j] and left is cur[j-1]. The base column now lives in each row's first entry, so set cur[0] = i before filling row i.

Turning word2 into word1 takes the same number of edits, since inserts and deletes trade places. Swap the words so the rows run along the shorter one: min(n, m) + 1 numbers per row instead of a table of up to 251,001 cells, with the same O(n × m) work.

Algorithm

If word2 is longer than word1, swap them.
Set prev = [0, 1, ..., m].
For each i from 1 to n, set cur[0] = i and fill cur[1..m] with the table rule, reading the diagonal and above from prev and the left from cur. Then 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

Filling row 0 and column 0 with zeros, as in longest common subsequence. Turning abc into an empty prefix costs 3 deletes, not 0.
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. With 1 + min(...) for equal letters, a into a costs 1.
Reading the left neighbor from prev instead of cur. Left is the insert of word2[j-1] in the current row.
Memoized recursion in Python on 500-letter words. The calls go up to 1000 deep, past the default recursion limit.

Frequently asked questions3

What is the time complexity of Edit Distance?

The table solution fills one cell per pair of prefixes in constant time: O(n × m) time for lengths n and m. 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?

This version is the Levenshtein distance: insert, delete and replace each cost one. Edit distance is the family name. 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.

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. Only the diagonal is lost, so save the old row[j] in a variable and use it as the diagonal for j + 1.

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

Test #1

Test #2

Test #3

Arguments

word1 = "spot"
word2 = "stop"

Expected Output

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 questions3

Similar problems