968 edit distance

The title is as follows

Here are two words for you word1 and word2, Please return to word1 convert to word2 The minimum number of operands used .

You can do the following three operations on a word ：

Insert a character
Delete a character
Replace a character

Example 1：
Input ：word1 = “horse”, word2 = “ros”
Output ：3
explain ：
horse -> rorse ( take ‘h’ Replace with ‘r’)
rorse -> rose ( Delete ‘r’)
rose -> ros ( Delete ‘e’)

Example 2：
Input ：word1 = “intention”, word2 = “execution”
Output ：5
explain ：
intention -> inention ( Delete ‘t’)
inention -> enention ( take ‘i’ Replace with ‘e’)
enention -> exention ( take ‘n’ Replace with ‘x’)
exention -> exection ( take ‘n’ Replace with ‘c’)
exection -> execution ( Insert ‘u’)

Tips ：
0 <= word1.length, word2.length <= 500
word1 and word2 It's made up of lowercase letters

Their thinking

Dynamic programming
We can do three operations on any word ：

Insert a character ;
Delete a character ;
Replace a character .

The title is given two words , Set to A and B, In this way, we can six operation methods .
But we can see , If we have words A And the words B：

Pairs of words A Delete a character and pair words B Inserting a character is equivalent . For example, when the word A by doge, word B by dog when , We can delete words A Last character of e, Get the same dog, You can also use words B Add a character at the end e, Get the same doge;

Empathy , Pairs of words B Delete a character and pair words A Inserting a character is also equivalent ;

Pairs of words A Replace a character and pair words B Replacing a character is equivalent . For example, when the word A by bat, word B by cat when , We modify words A First letter of b -> c, And modify words B First letter of c -> b It is equivalent. .

Since then , There are actually only three different operations ：
In the word A Insert a character in ;
In the word B Insert a character in ;
Modify the word A A character of .

Since then , We can turn the original problem into a smaller subproblem . We use it A = horse,B = ros As an example , Let's take a look at how to transform this problem into several smaller sub problems .

In the word A Insert a character in ： If we knew horse To ro The editing distance of is a, So clearly horse To ros Your editing distance will not exceed a + 1. This is because we can a After this operation, it will horse and ro Become the same string , Only additional 1 operations , In the word A Add characters at the end of s, You can be in a + 1 After this operation, it will horse and ro Become the same string ;

In the word B Insert a character in ： If we knew hors To ros The editing distance of is b, So clearly horse To ros Your editing distance will not exceed b + 1, The reason as above ;

Modify the word A A character of ： If we knew hors To ro The editing distance of is c, So clearly horse To ros Your editing distance will not exceed c + 1, The reason as above .

So from horse become ros The editing distance should be min(a + 1, b + 1, c + 1).

Be careful ： Why are we always talking about words A and B Insert or modify characters at the end of , Can it be operated in other places ？ The answer is yes , But we know that , The sequence of operations does not affect the final result . For example, for words cat, We hope that c and a Add characters between d And put the character t Change to character b, Then the two operations are in whatever order , Will get the final result cdab.

You may think horse To ro This problem is also difficult to solve . But it doesn't matter , We can continue to use the above method to split this problem , For all sub problems of this problem , We can also continue to split , until ：

character string A It's empty , If you follow The switch to ro, Obviously, the edit distance is a string B The length of , Here is 2;
character string B It's empty , If you follow horse The switch to , Obviously, the edit distance is a string A The length of , Here is 5.

therefore , We can use dynamic programming to solve this problem . We use it D[i][j] Express A Before i Letters and B Before j The edit distance between letters .

As mentioned above , When we get D[i][j-1],D[i-1][j] and D[i-1][j-1] After that, we can calculate D[i][j].

D[i][j-1] by A Before i Characters and B Before j - 1 Sub problem of character editing distance . That is for B Of the j Characters , We are A The same character is added at the end of the , that D[i][j] The minimum can be D[i][j-1] + 1;

D[i-1][j] by A Before i - 1 Characters and B Before j Sub problem of character editing distance . That is for A Of the i Characters , We are B The same character is added at the end of the , that D[i][j] The minimum can be D[i-1][j] + 1;

D[i-1][j-1] by A front i - 1 Characters and B Before j - 1 Sub problem of character editing distance . That is for B Of the j Characters , We modify A Of the i Two characters make them the same , that D[i][j] The minimum can be D[i-1][j-1] + 1. Specially , If A Of the i Characters and B Of the j The two characters are the same , Then we don't actually need to modify . under these circumstances ,D[i][j] The minimum can be D[i-1][j-1].

Then we can write the following state transition equation ：

So the results of each step will be based on the results of the previous step , It is shown as follows ：

For boundary cases , The edit distance between an empty string and a non empty string is D[i][0] = i and D[0][j] = j,D[i][0] It's equivalent to word1 perform i Delete operations ,D[0][j] It's equivalent to word1 perform j Insert operations .

To sum up, we get the whole process of the algorithm .

Solution code

class Solution 
{
    
public:
    int minDistance(string word1, string word2)
    {
    
        int n = word1.length();
        int m = word2.length();

        //  There is a string that is empty 
        if (n * m == 0) return n + m;

        // DP  Array 
        vector<vector<int>> D(n + 1, vector<int>(m + 1));

        //  Boundary state initialization 
        for (int i = 0; i < n + 1; i++)
        {
    
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++)
        {
    
            D[0][j] = j;
        }

        //  Calculate all  DP  value 
        for (int i = 1; i < n + 1; i++) 
        {
    
            for (int j = 1; j < m + 1; j++) 
            {
    
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (word1[i - 1] != word2[j - 1]) left_down += 1;
                D[i][j] = min(left, min(down, left_down));
            }
        }
        return D[n][m];
    }
};