Start learning free

LESSON 457 OF 541 · DYNAMIC PROGRAMMING

Edit Distance in Swift: 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 12
    Ctrl + Enter to check

    SWIFT · DYNAMIC PROGRAMMING

    Edit Distance in Swift, explained

    Problem overview

    The function minDistance(_ word1: String, _ word2: String) -> Int returns the fewest operations that turn word1 into word2. Three operations are allowed, and each counts as one: insert a character anywhere, delete a character, or replace a character with another one.

    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" the answer is 5, and for "" and "abc" it is 3, because the empty word needs three inserts. Both words hold lowercase letters a to z, up to 500 each, and either can be empty.

    Approach: a table of prefix distances

    Trying every sequence of operations is far too slow. Instead, solve smaller versions of the problem and reuse their answers. Let dp[i][j] be the fewest operations that turn the first i characters of word1 into the first j characters of word2. If m and n are the lengths of the words, 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.

    For the other entries, look at 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 dp[i][j] is 1 plus the smallest of three neighbours. dp[i - 1][j - 1] is a replace: both prefixes become one character shorter. dp[i - 1][j] is a delete of the last character of word1's prefix. dp[i][j - 1] is an insert of the character that matches the last one in word2's prefix, which then is one character shorter.

    Filling the table row by row, left to right, guarantees that the three neighbours (above, left and diagonally up-left) are filled before they are needed. For "horse" and "ros" the finished table 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 i belongs to the first i characters of horse, and column j to the first j characters of ros. The bottom right entry, 3, is the answer.

    Step by step

    1. Copy each word's bytes into an array with Array(word.utf8), stored in let constants chars1 and chars2. A Swift String can't be indexed by a number, and an array can. The words contain only a to z, one byte each, so comparing bytes compares letters.
    2. Store the lengths chars1.count and chars2.count in m and n. They come up in the table size and in all the loops.
    3. Create dp as a var: m + 1 rows, each an array of n + 1 zeros. The extra row and column are for the empty prefixes.
    4. Loop i over 0...m to fill column 0.
    5. Set dp[i][0] to i: i deletes empty the prefix.
    6. Loop j over 0...n to fill row 0.
    7. Set dp[0][j] to j: j inserts build the prefix. The entry dp[0][0] is written twice, both times with 0.
    8. Loop i over 1..<m + 1 for the remaining rows. Row 0 is done, so it starts at 1.
    9. Loop j over 1..<n + 1 inside it, for the same reason: column 0 is done.
    10. Equal last characters: compare chars1[i - 1] with chars2[j - 1]. The first i characters end at index i - 1, because the array counts from 0 while the table counts characters. If they match, copy dp[i - 1][j - 1].
    11. Different last characters: set dp[i][j] to 1 plus min of the replace, delete and insert neighbours. This is the key line.
    12. Return dp[m][n], which covers both words completely.

    The solution in Swift

    class Solution {
    func minDistance(_ word1: String, _ word2: String) -> Int {
        let chars1 = Array(word1.utf8)
        let chars2 = Array(word2.utf8)
        let m = chars1.count
        let n = chars2.count
        var dp = [[Int]](repeating: [Int](repeating: 0, count: n + 1), count: m + 1)
        for i in 0...m {
            dp[i][0] = i
        }
        for j in 0...n {
            dp[0][j] = j
        }
        for i in 1..<m + 1 {
            for j in 1..<n + 1 {
                if chars1[i - 1] == chars2[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]
    }
}

    The Swift details worth a closer look:

    • Bytes instead of characters. word.utf8 is a view of the string's UTF-8 bytes, and Array(...) turns it into a [UInt8]. For the lowercase letters in this lesson, one byte is one letter. Outside that range this would break: "héllo" has 5 characters but 6 bytes, so the byte-based function reports 2 operations between "héllo" and "hello", not 1. Using Array(word) would give an array of Character values, which also supports ==.
    • 1..<m + 1 and not 1...m. A closed range can't end before it starts. With an empty word1, m is 0, and 1...m would stop the program with a run-time error. The half-open 1..<1 is just empty, so the loop is skipped and the function returns dp[0][n]. The ranges 0...m and 0...n are fine, because they start at 0 and the lengths are never negative.
    • The table is made of copies. [Int](repeating: 0, count: n + 1) is a row, and [[Int]](repeating: row, count: m + 1) repeats it. Arrays are value types, so each row is an independent copy, and writing to dp[i][j] changes only that row.
    • min with three arguments. Swift's global min accepts any number of values, so no nesting is needed.
    • Operator precedence. In 1..<m + 1 the addition happens first, so the range ends before m + 1, which makes m the last row.

    Complexity

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

    Space: O(m · n). The whole table is kept. Each row only reads itself and the row above it, so two rows of n + 1 numbers would be enough and would bring the space down to O(n). The table is easier to follow, so the lesson keeps all of it.

    Edge cases and common mistakes

    • Empty words. minDistance("", "abc") is 3, minDistance("abc", "") is 3 and minDistance("", "") is 0. The initialised first row and column handle all three.
    • Off-by-one indexing. The table counts characters, and the arrays count from 0. The characters compared at dp[i][j] are chars1[i - 1] and chars2[j - 1]. Using chars1[i] goes out of bounds on the last row and stops the program.
    • Forgetting the base row and column. With zeros there, every distance comes out too small, because turning a prefix into an empty word would look free.
    • Taking the minimum of only two neighbours. Leaving out the replace case gives minDistance("a", "b") as 2 instead of 1.
    • Counting the 1 when the characters match. Equal last characters add nothing. Adding 1 anyway would turn minDistance("abc", "abc") into a nonzero answer.
    • Greedy thinking. Two operations are not enough for "horse" to "ros", and no quick rule such as comparing lengths finds the right count, which is why the table compares every prefix pair.

    Testing

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