Start learning free

LESSON 452 OF 536 · DYNAMIC PROGRAMMING

Edit Distance in Python: O(m · n) Dynamic Programming

Practice O(m · n) Read the full explanation

You are given two strings word1 and word2. Return the fewest operations that turn word1 into word2.

There are three operations, and each one counts as one:

  • Insert a character anywhere in the word.
  • Delete a character.
  • Replace a character with another one.

 

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (delete 'r')
rose -> ros (delete 'e')
Two operations are not enough: "ros" is two characters shorter, so both would have to be deletes, and deleting letters from "horse" never gives "ros", because its 'o' comes before its 'r'.

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (delete 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Example 3:

Input: word1 = "", word2 = "abc"
Output: 3
Explanation: The empty word becomes "abc" by inserting its 3 characters. Each operation adds at most one character, so no fewer will do.

 

Constraints:

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 are made of lowercase English letters only, a to z. Either of them can be empty.

Note:

Your algorithm should run in O(m · n) time and space, where m is the length of word1 and n the length of word2.



Trying every sequence of operations is far too slow. Solve smaller versions of the problem instead: let dp[i][j] be the fewest operations that turn the first i characters of word1 into the first j characters of word2. The table has (m + 1) × (n + 1) entries, and the answer is dp[m][n].
Row 0 and column 0 stand for an empty prefix. Turning i characters into nothing takes i deletes, so dp[i][0] = i; turning nothing into j characters takes j inserts, so dp[0][j] = j.

Fill the table row by row, so the entries above, to the left and diagonally up-left of dp[i][j] are already known. Look at the last characters of the two prefixes, word1[i - 1] and word2[j - 1]:
  • When they are equal, they need no operation: dp[i][j] = dp[i - 1][j - 1]. Spending an operation on either of them is never better.
  • When they differ, one operation fixes the end of the prefix, and dp[i][j] is 1 plus the smallest of three neighbours:
    • dp[i - 1][j - 1]: replace word1[i - 1] with word2[j - 1]; both prefixes are then one character shorter.
    • dp[i - 1][j]: delete word1[i - 1]; only the prefix of word1 is shorter.
    • dp[i][j - 1]: insert word2[j - 1] at the end; it matches the last character of word2's prefix, which is then one shorter.

The table has (m + 1) × (n + 1) entries, and each one takes a constant amount of work: O(m · n) time and O(m · n) space.
Each row reads only itself and the row above it, so two rows of n + 1 numbers are enough, which brings the space down to O(n). The lesson keeps the whole table, which is easier to follow.
STEP 1 OF 11
    Ctrl + Enter to check

    PYTHON · DYNAMIC PROGRAMMING

    Edit Distance in Python, explained

    Problem overview

    The function minDistance(word1, word2) returns the fewest operations that turn word1 into word2. There are three operations, each costing one: insert a character anywhere, delete a character, or replace a character with another. Both words are lowercase letters, up to 500 characters each, and either may be empty.

    For word1 = "horse" and word2 = "ros" the answer is 3: replace h with r to get rorse, delete the second r to get rose, then delete e. For "intention" and "execution" it is 5, and for "" and "abc" it is 3, three inserts.

    Approach: solve every pair of prefixes

    Trying every sequence of operations is hopeless, since the number of sequences explodes with the word lengths. The way in is to solve smaller versions of the same problem. Let dp[i][j] be the fewest operations that turn the first i characters of word1 into the first j characters of word2. With m = len(word1) and n = len(word2), the table has (m + 1) × (n + 1) entries and the answer is dp[m][n]. The extra row and column stand for the empty prefix.

    The edges of the table are easy:

    • dp[i][0] = i: turning i characters into nothing takes i deletes.
    • dp[0][j] = j: turning nothing into j characters takes j inserts.

    The rest is filled row by row, left to right, so the entries above, to the left and diagonally up-left of dp[i][j] are known when it is reached. The decision depends on the last characters of the two prefixes, word1[i - 1] and word2[j - 1]:

    • They are equal. They need no operation, so dp[i][j] = dp[i - 1][j - 1]. Spending an operation on either of them is never better.
    • They differ. One operation fixes the end, and the result is 1 plus the best of three neighbours:
      • dp[i - 1][j - 1] for a replace, after which both prefixes are one character shorter;
      • dp[i - 1][j] for a delete of word1's last character;
      • dp[i][j - 1] for an insert of word2's last character at the end, which then matches, so only word2's prefix gets shorter.

    For "horse" and "ros" the finished table is below. Rows are the prefixes of "horse" (the empty one first) and columns the prefixes of "ros".

    [0, 1, 2, 3]
[1, 1, 2, 3]
[2, 2, 1, 2]
[3, 2, 2, 2]
[4, 3, 3, 2]
[5, 4, 4, 3]

    The bottom-right entry, 3, is the answer.

    Step by step

    1. Store the lengths. m = len(word1) and n = len(word2), one per line, since both come up again and again.
    2. Build dp with a list comprehension. [[0] * (n + 1) for _ in range(m + 1)] creates a new row of n + 1 zeros for each of the m + 1 rows. The name _ says the loop variable isn't used.
    3. Loop i over range(m + 1) and set dp[i][0] = i. This fills column 0, the empty prefix of word2. It runs from 0 to m, since every row has an entry in that column.
    4. Loop j over range(n + 1) and set dp[0][j] = j. This fills row 0 the same way. The corner dp[0][0] is set twice, both times to 0.
    5. Loop i over range(1, m + 1). Row 0 is done, so the loop starts at 1, and range stops before its end, hence m + 1.
    6. Loop j over range(1, n + 1) inside it. Column 0 is already filled, so j starts at 1.
    7. If word1[i - 1] == word2[j - 1], copy the diagonal. The first i characters end at index i - 1: the word counts from 0, while the table counts characters.
    8. Otherwise take 1 plus the min of the three neighbours. min accepts any number of arguments, so min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) covers replace, delete and insert. The 1 counts the operation itself.
    9. Return dp[m][n]. It covers all of both words.

    The solution in Python

    class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = i
        for j in range(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:
                    dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]

    Python details that matter here:

    • Build the rows separately. [[0] * (n + 1)] * (m + 1) looks equivalent, but it repeats one row object m + 1 times. Assigning to one cell then shows up in every row. With a 3 by 3 table made that way, setting bad[0][1] = 9 gives [[0, 9, 0], [0, 9, 0], [0, 9, 0]]. The comprehension runs [0] * (n + 1) once per row, so each row is its own list.
    • Strings index from 0. word1[i - 1] is the i-th character. Strings are immutable, so the code never changes the words; it only reads them.
    • Empty words are fine. len("") is 0, so the loops over range(1, m + 1) or range(1, n + 1) are empty and the answer comes straight from the edge of the table.

    Complexity

    The table has (m + 1) × (n + 1) entries, and each one takes constant work, so the time is O(m · n) and the space is O(m · n). Each row reads only itself and the row above, so keeping two rows would bring the space down to O(n). The lesson keeps the whole table because it is easier to follow, and because the table can be printed and checked by hand.

    Edge cases and common mistakes

    • One empty word. minDistance("", "abc") and minDistance("abc", "") are both 3, and two empty words give 0. The edges of the table handle all of these.
    • Identical words. minDistance("same", "same") is 0: every pair of last characters matches, so the diagonal carries 0 to the end.
    • Off-by-one with the indexes. The table entry dp[i][j] is about i characters, so the characters to compare are at i - 1 and j - 1. Comparing word1[i] with word2[j] reads the wrong characters and fails at the last index.
    • Forgetting the +1. When the characters differ, taking the min of the neighbours alone would count the fix as free.
    • Treating a swap as one operation. There is no swap: "ab" to "ba" costs 2, two replaces.
    • Filling in the wrong order. Row by row with j increasing guarantees that the three neighbours exist. Filling column by column works as well, but mixing the directions does not.

    Testing

    minDistance("horse", "ros")          -> 3
minDistance("intention", "execution") -> 5
minDistance("", "abc")               -> 3
minDistance("abc", "")               -> 3
minDistance("", "")                  -> 0
minDistance("ab", "ba")              -> 2
minDistance("kitten", "sitting")     -> 3
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free