Start learning free

LESSON 456 OF 540 · DYNAMIC PROGRAMMING

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

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 12
    Ctrl + Enter to check

    GO · DYNAMIC PROGRAMMING

    Edit Distance in Go, explained

    Problem overview

    The function minDistance takes two strings, word1 and word2, and returns the fewest operations that turn word1 into word2. Three operations exist and each costs one: insert a character anywhere, delete a character, or replace a character with another one. Both words are lowercase letters, and either can be empty.

    For word1 = "horse" and word2 = "ros" the answer is 3: replace h with r, delete the second r, delete e. For "intention" and "execution" it is 5. For "" and "abc" it is 3, three inserts, because each operation adds at most one character.

    Approach: solve every pair of prefixes

    Trying every sequence of operations explodes quickly. The better idea is to solve smaller versions of the same question and reuse the answers.

    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 an empty prefix.

    The borders are easy. 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.

    For an inner entry, look at the last characters of the two prefixes, word1[i-1] and word2[j-1]:

    • They are equal. That pair needs no operation, so dp[i][j] = dp[i-1][j-1]. Spending an operation on either character is never better.
    • 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] is a replace, which leaves both prefixes one shorter. dp[i-1][j] is a delete of word1's last character. dp[i][j-1] is an insert of word2's last character at the end, which matches it and leaves only word2's prefix shorter.

    Filling the table row by row, left to right, means the cell above, the cell to the left and the cell diagonally up-left are all ready when you reach dp[i][j].

    Step by step

    1. Store the lengths in m and n. They appear in every loop bound.
    2. Create the table as make([][]int, m+1): m+1 rows, each still nil.
    3. Loop over the rows with range, keeping only the index i, so that rows and column 0 are filled together.
    4. Give each row n+1 zeros with make([]int, n+1).
    5. Set dp[i][0] = i. Column 0 is the empty prefix of word2, and i characters need i deletes.
    6. Fill row 0 with a loop for j from 0 to n.
    7. Set dp[0][j] = j. Building j characters from nothing takes j inserts. dp[0][0] is written twice, both times with 0.
    8. Start the main loop over rows at i = 1 up to m. Row 0 is already filled.
    9. Loop over the columns from j = 1 up to n. Column 0 is also filled.
    10. If the last characters are equal, copy the diagonal: dp[i][j] = dp[i-1][j-1]. The prefix of length i ends at index i-1, which is why the characters are read at i-1 and j-1.
    11. Otherwise set dp[i][j] to 1 + min(...) of the replace, delete and insert neighbours. This is the key line.
    12. Return dp[m][n], which covers all of both words.

    The solution in Go

    func minDistance(word1 string, word2 string) int {
    m := len(word1)
    n := len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            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]
}

    For "horse" and "ros" the finished table, one line per row, is:

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

    Row 0 is the empty prefix of "horse", and column 0 is the empty prefix of "ros". The bottom-right entry, 3, is the answer.

    The Go details worth a closer look:

    • A table is a slice of slices. Go has no built-in two-dimensional slice. make([][]int, m+1) creates only the outer slice, whose rows are nil, and each row has to be created with its own make. Indexing a nil row would panic, which is why the row loop comes first.
    • for i := range dp with one variable gives the index only, from 0 to m.
    • Bytes, not characters. word1[i-1] is a byte, and len(word1) counts bytes. For lowercase English letters that is the same as characters. For text with accents or other non-ASCII letters the code would compare bytes: minDistance("é", "e") returns 2, because é takes two bytes. Converting the words with []rune(word) would count characters instead.
    • Built-in min. Since Go 1.21 the built-in min takes any number of values, so it needs no import and no helper function. Here it takes three.
    • Comparing bytes. word1[i-1] == word2[j-1] compares two byte values directly, so no conversion is needed.

    Complexity

    Time: O(m · n). The table has (m + 1) × (n + 1) entries, and each is computed once with a constant amount of work.

    Space: O(m · n). The lesson keeps the whole table because it is easier to follow. Each row reads only itself and the row above it, so two rows of n + 1 numbers would be enough for O(n) space if you only need the number and not the table.

    Edge cases and common mistakes

    • Empty words. minDistance("", "abc") and minDistance("abc", "") both return 3, and two empty words return 0. The loops over the inner entries don't run, and the border values already hold the answer.
    • Identical words. minDistance("abc", "abc") returns 0: every pair of last characters matches and the diagonal carries 0 down to the corner.
    • Off-by-one on the characters. The table counts characters while the strings count from 0. Writing word1[i] instead of word1[i-1] compares the wrong characters, and at i = m it runs past the end of the string and panics.
    • Forgetting the borders. If row 0 and column 0 stay at zero, every comparison against an empty prefix reports 0 operations, and the answers come out too small.
    • Taking the minimum of two neighbours only. All three moves are needed. Leaving out the diagonal means no replace, so "horse" to "ros" could not use its first operation.
    • Forgetting the 1. When the characters differ, the operation itself costs one on top of the neighbour's value.
    • Swapped letters. minDistance("ab", "ba") returns 2: there is no swap operation, so it takes two replaces.

    Testing

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