【LeetCode每日一题】——72.编辑距离

一【题目类别】

• 字符串

二【题目难度】

• 困难

三【题目编号】

• 72.编辑距离

四【题目描述】

• 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
• 你可以对一个单词进行如下三种操作：
  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

五【题目示例】

• 示例 1：

  • 输入：word1 = “horse”, word2 = “ros”
  • 输出：3
  • 解释：
    • horse -> rorse (将 ‘h’ 替换为 ‘r’)
    • rorse -> rose (删除 ‘r’)
    • rose -> ros (删除 ‘e’)

• 示例 2：

  • 输入：word1 = “intention”, word2 = “execution”
  • 输出：5
  • 解释：
    • intention -> inention (删除 ‘t’)
    • inention -> enention (将 ‘i’ 替换为 ‘e’)
    • enention -> exention (将 ‘n’ 替换为 ‘x’)
    • exention -> exection (将 ‘n’ 替换为 ‘c’)
    • exection -> execution (插入 ‘u’)

六【解题思路】

• 本题较困难，利用动态规划的思想
• 首先定义$dp[i][j]$表示$word1$的前$i$个字符和$word2$的前$j$个字符之间的编辑距离
• 之后分两种情况：
  • $word1$的前$i$个字符和$word2$的前$j$个字符不相同：
    • 插入一个字符：$dp[i][j]=dp[i][j-1]$
    • 删除一个字符：$dp[i][j]=dp[i-1][j]$
    • 替换一个字符：$dp[i][j]=dp[i-1][j-1]$
    • 不管是以上哪种，都需要$+1$，因为都是一步操作
  • $word1$的前$i$个字符和$word2$的前$j$个字符相同：
    • 取$dp[i][j]$和$dp[i-1][j-1]$之间的最小值，因为$word1$的前$i$个字符和$word2$的前$j$个字符相同，说明不需要操作
• 还需要注意一些细节，初始化第一列为$i$（遍历$word1$），因为$word1$的每步字符串变为长度为$0$都需要$i$步；初始化第一行为$j$（遍历$word2$），因为$word2$的每步字符串变为长度为$0$都需要$j$步
• 最后返回$dp[m][n]$即可，其中$m、n$分别为两个字符串的长度

七【题目提示】

• $0<=word1.length,word2.length<=500$
• $word1和word2由小写英文字母组成$

八【时间频度】

• 时间复杂度：$O(mn)$，其中$m、n$分别为两个字符串的长度
• 空间复杂度：$O(mn)$，其中$m、n$分别为两个字符串的长度

九【代码实现】

1. Java语言版

package String;

/**
 * @Author: IronmanJay
 * @Description: 72.编辑距离
 * @CreateTime: 2022-12-03  10:27
 */
public class p72_EditDistance {

    public static void main(String[] args) {
        String word1 = "horse";
        String word2 = "ros";
        int res = minDistance(word1, word2);
        System.out.println("res = " + res);
    }

    public static 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 + 1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i < n + 1; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j]);
                }
            }
        }
        return dp[m][n];
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

2. C语言版

#include
#include

int minDistance(char * word1, char * word2)
{
	int dp[501][501];
	int m = strlen(word1);
	int n = strlen(word2);
	dp[0][0] = 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++)
		{
			dp[i][j] = fmin(dp[i][j - 1], fmin(dp[i - 1][j], dp[i - 1][j - 1])) + 1;
			if (word1[i - 1] == word2[j - 1])
			{
				dp[i][j] = fmin(dp[i][j], dp[i - 1][j - 1]);
			}
		}
	}
	return dp[m][n];
}

/*主函数省略*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

十【提交结果】

1. Java语言版
   

2. C语言版