一、题目描述

给你两个单词 word1 和 word2，请返回将 word1 转换为 word2 所使用的最少操作数。

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

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

---

二、解题思路

1. 问题分析

• 这是一个最优子结构问题，适合用动态规划解决。
• 假设将 word1 转换成 word2 的最少操作数为 dp[i][j]，表示将 word1[0...i-1] 转换成 word2[0...j-1] 的最小编辑距离。

2. 状态转移方程

1. 如果 word1[i-1] == word2[j-1]：
   • 当前字符相同，不需要操作，dp[i][j] = dp[i-1][j-1]。
2. 如果 word1[i-1] != word2[j-1]：
   • 可以进行三种操作，选择操作数最小的一种：
     • 插入字符：dp[i][j] = dp[i][j-1] + 1
     • 删除字符：dp[i][j] = dp[i-1][j] + 1
     • 替换字符：dp[i][j] = dp[i-1][j-1] + 1

3. 边界条件

• 当 i == 0 时，dp[i][j] = j，表示将空字符串转换为 word2[0...j-1] 需要插入 j 个字符。
• 当 j == 0 时，dp[i][j] = i，表示将 word1[0...i-1] 转换为空字符串需要删除 i 个字符。

---

三、代码实现

动态规划实现（C语言）

#include <stdio.h>
#include <string.h>
#include <stdlib.h>int min(int a, int b, int c) {int minVal = a < b ? a : b;return minVal < c ? minVal : c;
}int minDistance(char *word1, char *word2) {int m = strlen(word1);int n = strlen(word2);// 创建 DP 数组int **dp = (int **)malloc((m + 1) * sizeof(int *));for (int i = 0; i <= m; i++) {dp[i] = (int *)malloc((n + 1) * sizeof(int));}// 初始化边界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] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;}}}// 最终结果int result = dp[m][n];// 释放内存for (int i = 0; i <= m; i++) {free(dp[i]);}free(dp);return result;
}int main() {char word1[100], word2[100];printf("请输入第一个单词：");scanf("%s", word1);printf("请输入第二个单词：");scanf("%s", word2);int result = minDistance(word1, word2);printf("最小编辑距离为：%d\n", result);return 0;
}

---

这段代码的作用是更新二维动态规划数组 dp 的值，根据三种可能的操作选择最优解。我们逐项解释：

---

上下文：动态规划的含义

• dp[i][j] 表示将 word1[0...i-1] 转换为 word2[0...j-1] 的最小操作数。
• 在 word1[i-1] != word2[j-1] 的情况下，当前状态 dp[i][j] 的值需要通过三种操作之一得到：
  1. 插入操作：将 word2[j-1] 插入到 word1[0...i-1] 中；
  2. 删除操作：将 word1[i-1] 从 word1[0...i-1] 中删除；
  3. 替换操作：将 word1[i-1] 替换为 word2[j-1]。

---

具体公式分析

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;

三个子问题：

1. 删除操作：
   如果选择删除 word1[i-1]，只需要考虑将 word1[0...i-2] 转换为 word2[0...j-1] 的最优解，然后加 1（删除操作的代价）：
   [
   dp[i][j] = dp[i-1][j] + 1
   ]

2. 插入操作：
   如果选择插入 word2[j-1]，只需要考虑将 word1[0...i-1] 转换为 word2[0...j-2] 的最优解，然后加 1（插入操作的代价）：
   [
   dp[i][j] = dp[i][j-1] + 1
   ]

3. 替换操作：
   如果选择将 word1[i-1] 替换为 word2[j-1]，只需要考虑将 word1[0...i-2] 转换为 word2[0...j-2] 的最优解，然后加 1（替换操作的代价）：
   [
   dp[i][j] = dp[i-1][j-1] + 1
   ]

最优选择：

我们取三种操作中最小的代价：
[
dp[i][j] = \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1}) + 1
]

---

特殊情况：当 word1[i-1] == word2[j-1]

如果当前字符相等，不需要任何操作，dp[i][j] = dp[i-1][j-1]。

---

示例分析

示例 1：

word1 = "horse", word2 = "ros"

填表过程：

		r	o	s
	0	1	2	3
h	1	1	2	3
o	2	2	1	2
r	3	2	2	2
s	4	3	3	2
e	5	4	4	3

最终结果为 dp[5][3] = 3。

---

示例 2：

word1 = "intention", word2 = "execution"

填表可以类似完成，逐步根据状态转移公式填充每个 dp[i][j] 的值。

---

四、复杂度分析

时间复杂度

• 填充一个大小为 $m\times n$ 的 DP 表，其中 $m=\text{len(word1)}$，$n=\text{len(word2)}$。
• 总时间复杂度为 $O(m\times n)$。

空间复杂度

• DP 表占用 $O(m\times n)$ 的空间。
• 如果进一步优化，可以使用滚动数组将空间复杂度优化为 $O(\min (m,n))$。

---

五、运行示例

示例 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')