题目描述
给定两个单词 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版本
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// 创建一个二维数组dp
int[][] 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);
// 创建一个二维数组dp
int 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)
# 创建一个二维数组dp
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始化第一行和第一列
for i in range(m + 1):
dp[i][0] = i
for 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 main
import (
"fmt"
"math"
)
func minDistance(word1 string, word2 string) int {
m, n := len(word1), len(word2)
// 创建一个二维数组dp
dp := 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 |