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

题目描述

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

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

插入一个字符
删除一个字符
替换一个字符

原题：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版本

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版本

python">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
}