Start learning free

LESSON 451 OF 535 · DYNAMIC PROGRAMMING

Edit Distance in C++: Dynamic Programming on Prefixes

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

    C++ · DYNAMIC PROGRAMMING

    Edit Distance in C++, explained

    Problem overview

    The function minDistance receives 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. Either word can be empty, and both use only lowercase letters.

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

    Approach: solve for every pair of prefixes

    Trying every sequence of operations is far too slow, since each step has many choices. The statement asks for O(m * n) time, where m and n are the word lengths, which points to solving smaller versions of the problem and reusing them.

    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], the entry for both whole words.

    The first row and column are the easy cases, where one prefix is empty. 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 rest, 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 must fix the end, and there are three ways to do it:
      • replace: dp[i - 1][j - 1], with both prefixes one character shorter;
      • delete the character from word1: dp[i - 1][j];
      • insert word2's last character at the end: dp[i][j - 1], since the new character matches and only word2's prefix gets shorter.
      Then dp[i][j] is 1 plus the smallest of those three.

    Filling the table row by row and left to right means all three neighbours are ready when an entry is computed. Here is the table for "cat" and "cut". Rows are the prefixes of "cat" from empty to whole, columns the prefixes of "cut":

    0 1 2 3
1 0 1 2
2 1 1 2
3 2 2 1

    The bottom-right entry is 1: replace a with u.

    Step by step

    1. Store the lengths of the words in int variables m and n. They are used for the table size and the loops.
    2. Create dp as a vector<vector<int>> with m + 1 rows, each a vector<int> of n + 1 zeros. The extra row and column stand for the empty prefix.
    3. Fill column 0 with a loop over i from 0 to m, setting dp[i][0] to i: that many deletes.
    4. Fill row 0 with a loop over j from 0 to n, setting dp[0][j] to j: that many inserts. dp[0][0] is set twice, both times to 0.
    5. Loop over the rest of the table: i from 1 to m, and inside it j from 1 to n. Row 0 and column 0 are done, so both start at 1.
    6. If the last characters are equal, copy dp[i - 1][j - 1]. The first i characters end at index i - 1, because the string counts from 0 while the table counts characters.
    7. Otherwise set dp[i][j] to 1 plus the smallest of the replace, delete and insert neighbours. The min function compares two values, so two nested calls pick the smallest of three.
    8. Return dp[m][n] after the loops.

    The solution in C++

    class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int 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], min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }
        return dp[m][n];
    }
};

    The C++ details worth a closer look:

    • size() and int. word1.size() returns an unsigned type, and assigning it to an int converts it. That is fine for words of up to 500 characters. The conversion matters elsewhere: for an empty string, word.size() - 1 does not give -1 but 18446744073709551615, because unsigned arithmetic wraps. The code avoids that by storing the lengths as int and never subtracting from size().
    • Building the table. vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)) makes m + 1 copies of one row of n + 1 zeros. The closing >> of the type is fine in C++11 and later.
    • Passing by value. minDistance takes the strings by value, so the function works on copies. It only reads them, so a const string& would also work, but the signature stays as the lesson has it.
    • word1[i - 1] reads a char, and comparing two char values with == compares the characters themselves, not addresses.
    • Two min calls. std::min takes two arguments. An initializer list version, min({a, b, c}), also exists, but nesting two calls is enough.

    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, so two rows would be enough and bring the space down to O(n), but the full table is easier to follow.

    Edge cases and common mistakes

    • Empty words. minDistance("", "abc") returns 3 and minDistance("abc", "") returns 3 as well. Two empty words give 0, because the table has a single entry, dp[0][0].
    • Equal words. "abc" and "abc" give 0: every entry on the diagonal copies the one before it.
    • Index off by one. The table entry dp[i][j] is about i characters, so the last one is word1[i - 1]. Using word1[i] compares the character after the one the entry ends on, and the answer is wrong.
    • Forgetting the 1. In the else branch the operation itself costs one. Without it, mismatching characters would be free.
    • Starting the main loops at 0. Then i - 1 or j - 1 is -1 and the code indexes before the start of the string and the row.

    Testing

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