Start learning free

LESSON 459 OF 543 · DYNAMIC PROGRAMMING

Edit Distance in Rust: 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

    RUST · DYNAMIC PROGRAMMING

    Edit Distance in Rust, explained

    Problem overview

    The function min_distance receives two strings, word1 and word2, and returns the fewest operations that turn word1 into word2. The operations are insert a character anywhere, delete a character, and replace a character with another one. Each costs 1. Both words use lowercase letters a to z and either can be empty.

    For "horse" and "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. For "" and "abc" it is 3, three inserts.

    Approach: the table of prefix distances

    Trying every sequence of operations is far too slow. The lesson solves smaller versions of the problem and builds on them. 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 and n the two lengths, 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.

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

    • If they are equal, they need no operation, and dp[i][j] = dp[i - 1][j - 1]. Spending an operation on either of them is never better.
    • If 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 lose their last character. 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 then matches and leaves a shorter prefix of word2.

    For "horse" and "ros", the rows 1 to 5 of the table (columns for the prefixes of "ros", from the empty one) are:

    row 1 (h)      [1, 1, 2, 3]
row 2 (ho)     [2, 2, 1, 2]
row 3 (hor)    [3, 2, 2, 2]
row 4 (hors)   [4, 3, 3, 2]
row 5 (horse)  [5, 4, 4, 3]

    The bottom-right entry, 3, is the answer. Row 0 is [0, 1, 2, 3].

    Step by step

    1. Take the bytes of each word with as_bytes(). Rust doesn't index a String by position, but a byte slice can be indexed. The letters a to z take one byte each, so comparing bytes compares letters.
    2. Store the lengths in m and n. They are used for the table size and the loop bounds.
    3. Create the table dp with m + 1 rows of n + 1 zeros, written 0i32 so the entries have the return type. The extra row and column are the empty prefixes.
    4. Fill column 0 with a loop of i over 0..=m.
    5. Set dp[i][0] to i as i32. Turning i characters into an empty word takes i deletes. The cast turns the usize index into the table's number type.
    6. Fill row 0 with a loop of j over 0..=n.
    7. Set dp[0][j] to j as i32, the j inserts. The corner dp[0][0] is set twice, both times to 0.
    8. Loop over the rows with i over 1..=m, since row 0 is done.
    9. Loop over the columns with j over 1..=n. Going row by row and left to right means the three neighbours are already filled.
    10. Compare the last characters, bytes1[i - 1] and bytes2[j - 1]. The first i characters end at index i - 1, because the slice counts from 0 and the table counts characters. If they are equal, copy dp[i - 1][j - 1].
    11. Otherwise take 1 plus the smallest neighbour with min chained twice. This is the key line: it chooses between replace, delete and insert.
    12. Return dp[m][n] as the last expression.

    The solution in Rust

    impl Solution {
    fn min_distance(word1: String, word2: String) -> i32 {
        let bytes1 = word1.as_bytes();
        let bytes2 = word2.as_bytes();
        let m = bytes1.len();
        let n = bytes2.len();
        let mut dp = vec![vec![0i32; n + 1]; m + 1];
        for i in 0..=m {
            dp[i][0] = i as i32;
        }
        for j in 0..=n {
            dp[0][j] = j as i32;
        }
        for i in 1..=m {
            for j in 1..=n {
                if bytes1[i - 1] == bytes2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + dp[i - 1][j - 1].min(dp[i - 1][j]).min(dp[i][j - 1]);
                }
            }
        }
        dp[m][n]
    }
}

    The Rust details worth a closer look:

    • vec![vec![0i32; n + 1]; m + 1]. The outer vec! clones the inner row for every slot, so each row is its own vector and changing one row doesn't affect another.
    • as_bytes() and strings. A String is UTF-8 and has no word1[i]. Indexing bytes is correct here only because the words are ASCII lowercase letters. For text with other characters, a byte is not a character, and you would collect chars() into a vector instead.
    • usize indexes. Vector indexes are usize, which can't go below zero. The loops start at 1 whenever the body reads i - 1 or j - 1, so those subtractions never underflow. The values stored in the table are i32, hence i as i32.
    • a.min(b).min(c). min is a method on integers. Chaining it twice gives the smallest of three. The expression 1 + dp[i - 1][j - 1].min(...).min(...) adds 1 to that result, because method calls bind tighter than +.
    • Empty words. If word1 is empty, then m is 0, the loops over 1..=m don't run, and the answer is dp[0][n], which is n. Inclusive ranges such as 1..=0 are simply empty.

    Complexity

    Time: O(m · n). The table has (m + 1) × (n + 1) entries, and each one is computed 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, so two rows of n + 1 numbers would be enough and bring the space down to O(n).

    Edge cases and common mistakes

    • One or both words empty. "" to "abc" is 3, "abc" to "" is 3, and "" to "" is 0.
    • Identical words. "abc" to "abc" is 0: every comparison matches and the diagonal carries the 0 from the corner.
    • Off-by-one on the characters. The table entry dp[i][j] is about the first i characters, whose last one is bytes1[i - 1]. Comparing bytes1[i] reads one character too far, and for i = m it panics with an index out of bounds.
    • Counting a replace as two operations. A replace is one operation. "a" to "b" is 1, not 2.
    • Skipping the delete or insert case. Using only the replace neighbour fails whenever the words differ in length: "horse" to "ros" needs two deletes.
    • Greedy matching. Pairing equal letters from the left does not give the right answer in general. The table compares all the alternatives at every cell instead.

    Testing

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