【经典算法】LeetCode 72. 编辑距离(Java/C/Python3/Go实现含注释说明,中等)

题目描述

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

原题：LeetCode 72

思路及实现

方式一：动态规划

思路

使用二维数组 dp 来保存子问题的解，其中 dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符所需要的最少操作数。

• 当 word1[i-1] == word2[j-1] 时，不需要进行操作，dp[i][j] = dp[i-1][j-1]。
• 当 word1[i-1] != word2[j-1] 时，可以选择插入、删除或替换操作，取这三种操作的最小值加1，即 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

代码实现

Java版本

public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();// 创建一个二维数组dpint[][] dp = new int[m + 1][n + 1];// 初始化第一行和第一列for (int i = 0; i <= m; i++) {dp[i][0] = i;}for (int j = 0; j <= n; j++) {dp[0][j] = j;}// 填充dp数组for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));}}}return dp[m][n];
}

说明：Java版本使用了二维数组dp来保存中间结果，并通过循环填充该数组。

C语言版本

#include <stdio.h>
#include <string.h>
#include <limits.h>int minDistance(char *word1, char *word2) {int m = strlen(word1);int n = strlen(word2);// 创建一个二维数组dpint dp[m + 1][n + 1];// 初始化第一行和第一列for (int i = 0; i <= m; i++) {dp[i][0] = i;}for (int j = 0; j <= n; j++) {dp[0][j] = j;}// 填充dp数组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 + fmin(fmin(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]);}}}return dp[m][n];
}

说明：C语言版本与Java版本类似，但使用了fmin函数来取最小值。

Python3版本

def minDistance(word1: str, word2: str) -> int:m, n =len(word1), len(word2)# 创建一个二维数组dpdp = [[0] * (n + 1) for _ in range(m + 1)]# 初始化第一行和第一列for i in range(m + 1):dp[i][0] = ifor j in range(n + 1):dp[0][j] = j# 填充dp数组for i in range(1, m + 1):for j in range(1, n + 1):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], dp[i - 1][j], dp[i][j - 1])return dp[m][n]

说明：Python3版本使用列表推导式创建二维数组，并使用min函数来取最小值。

Golang版本

package mainimport ("fmt""math"
)func minDistance(word1 string, word2 string) int {m, n := len(word1), len(word2)// 创建一个二维数组dpdp := make([][]int, m+1)for i := range dp {dp[i] = make([]int, n+1)}// 初始化第一行和第一列for i := 0; i <= m; i++ {dp[i][0] = i}for j := 0; j <= n; j++ {dp[0][j] = j}// 填充dp数组for i := 1; i <= m; i++ {for 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 + int(math.Min(float64(dp[i-1][j-1]), math.Min(float64(dp[i-1][j]), float64(dp[i][j-1]))))}}}return dp[m][n]
}func main() {word1 := "horse"word2 := "ros"fmt.Println(minDistance(word1, word2)) // 输出: 3
}

说明：Golang版本使用make函数创建二维切片，并使用math.Min函数来取最小值。

复杂度分析

• 时间复杂度：O(m * n)，其中m和n分别是两个单词的长度。因为我们需要遍历两个单词的所有字符。
• 空间复杂度：O(m * n)，用于保存子问题的解。

总结

方式	优点	缺点	时间复杂度	空间复杂度
方式一	逻辑清晰，易于实现	需要额外的空间来保存子问题的解	O(m * n)	O(m * n)

相似题目

相似题目	难度	链接
leetcode 10	中等	力扣-10
leetcode 1143	中等	力扣-1143
leetcode 647	中等	力扣-647