leetcode 72. Edit distance edit distance (medium)

One 、 The main idea of the topic

label :  Dynamic programming

https://leetcode.cn/problems/edit-distance

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

Two 、 Their thinking

Use a two-dimensional array dp[i][j], Represents the first string to position i until , And the second string to position j until , It takes at most a few steps to edit . When the first i Position and number j When the characters corresponding to bits are the same ,dp[i][j] be equal to dp[i-1][j-1]; When the corresponding characters are different , The cost of modification is dp[i-1][j-1]+1, Insert i Location / Delete j The consumption of location is dp[i][j-1]+1, Insert j Location / Delete i Location consumption is dp[i-1][j]+1.

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
 public int minDistance(String word1, String word2) {
 int m = word1.length();
 int n = word2.length();
 int[][] dp = new int[m + 1][n + 1];
 for (int i = 0; i <= m; i++) {
 for (int j = 0; j <= n; j++) {
 if (i == 0) {
 dp[i][j] = j;
 } else if (j == 0) {
 dp[i][j] = i;
 } else {
 dp[i][j] = Math.min(
 dp[i - 1][j - 1] + (word1.charAt(i - 1) == word2.charAt(j - 1) ? 0 : 1),
 Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
 );
 }
 }
 }
 return dp[m][n];
 }
}


Four 、 Summary notes

• 2022/7/4  Stick to one question every day