72. 编辑距离

🟠   🔖  字符串 动态规划  🔗 力扣 LeetCode

题目

Given two strings word1 and word2, return the minimum number of operations required to convertword1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"

Output: 3

Explanation:

horse -> rorse (replace 'h' with 'r')

rorse -> rose (remove 'r')

rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"

Output: 5

Explanation:

intention -> inention (remove 't')

inention -> enention (replace 'i' with 'e')

enention -> exention (replace 'n' with 'x')

exention -> exection (replace 'n' with 'c')

exection -> execution (insert 'u')

Constraints:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

题目大意

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

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

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

word1 和 word2 由小写英文字母组成。

解题思路

可以从后往前挨个字符对比 s1 和 s2，对于每对字符 s1[i] 和 s2[j]，可以有四种操作：

if (s1[i] == s2[j]) {
  啥都别做（skip）
  i, j 同时向前移动
} else {
  三选一：
    1. 插入（Insert）： 在字符串 `s1` 的末尾插入一个字符，使其与字符串 `s2` 匹配。
    2. 删除（Delete）： 删除字符串 `s1` 的末尾字符，使其与字符串 `s2` 匹配。
    3. 替换（Replace）： 将字符串 `s1` 的末尾字符替换为另一个字符，使其与字符串 `s2` 匹配。
}

这个「三选一」到底该怎么选择呢？很简单，全试一遍，哪个操作最后得到的编辑距离最小，就选谁。

具体解法可以分为 递归 和 DP-table 两种方式。

思路一：动态规划-递归

使用递归来解题的思路如下：

• 定义一个递归函数 helper(i, j) ，用一个数组 dp 记录子问题的结果，避免重复计算；

• base case 是 i 走完 s1 或 j 走完 s2，可以直接返回另一个字符串剩下的长度；

• 如果 dp[i][j] 已经存在，则直接返回，否则就递归计算：

  • 若 s1[i] == s2[j]，说明此对字符本来就相等，不需要任何操作，递归计算 dp[i][j] = helper(i - 1, j - 1);

  • 否则取以下三种情况的最小值，别忘了操作数加一：dp[i][j] = Math.min(helper(i, j - 1), helper(i - 1, j), helper(i - 1, j - 1)) + 1;

    1. 插入（Insert）： helper(i, j - 1)，在 s1[i] 插入一个和 s2[j] 一样的字符，那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比；
    2. 删除（Delete）： helper(i - 1, j)，把 s[i] 这个字符删掉，前移 i，继续跟 j 对比；
    3. 替换（Replace）： helper(i - 1, j - 1)，把 s1[i] 替换成 s2[j]，那么 s2[j] 就被匹配了，同时前移 i，j 继续对比；

• 最后调用递归函数即可。

复杂度分析

• 时间复杂度：O(m * n)，其中 m 是 word1 的长度，n 是 word2 的长度。动态规划的状态空间为 m × n，每个状态通过递归函数调用进行填充，虽然每个状态的计算是通过递归实现的，但由于使用了记忆化搜索（动态规划），每个状态仅计算一次。因此，总的时间复杂度为 O(m * n)。

• 空间复杂度：O(m * n)，用于存储动态规划表 dp，该表的大小为 m × n，记录每个子问题的结果。此外，递归调用栈的深度也可能达到 O(m + n)，但这是常量因素，因此主要的空间复杂度来源于 dp 数组。

---

思路二：动态规划-DP table

定义一个二维数组 dp , dp[i][j] 表示将长度为 i 的字符串 s1 转换为长度为 j 的字符串 s2 所需的最小编辑距离。dp[..][0] 和 dp[0][..] 对应 base case。

状态转移方程如下：

• 当 s1[i-1] === s2[j-1]，即当前字符相同：dp[i][j] = dp[i-1][j-1]
• 否则，取以下操作的最小值：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

其中，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作，dp[i-1][j-1] 表示替换操作。

DP table 和递归的思路大致相同，唯一不同的是，DP table 是自底向上求解，递归解法是自顶向下求解。递归函数的 base case 是 i, j 等于 -1，而 DP table 的数组索引至少是 0，所以 DP table 数组会偏移一位。

复杂度分析

• 时间复杂度：O(m * n)，其中 m 是 word1 的长度，n 是 word2 的长度。动态规划需要循环遍历 m × n 次。

• 空间复杂度：O(m * n)，用于存储动态规划表 dp，该表的大小为 m × n，记录每个子问题的结果。

代码

动态规划-递归

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
	const m = word1.length;
	const n = word2.length;
	let dp = new Array(m).fill(-1).map((i) => new Array(n).fill(-1));
	const helper = (i, j) => {
		// base case
		if (i == -1) return j + 1;
		if (j == -1) return i + 1;

		if (dp[i][j] != -1) {
			return dp[i][j];
		}

		if (word1.charAt(i) == word2.charAt(j)) {
			dp[i][j] = helper(i - 1, j - 1); // 跳过
		} else {
			dp[i][j] =
				Math.min(
					helper(i, j - 1), // 插入
					helper(i - 1, j), // 删除
					helper(i - 1, j - 1) // 替换
				) + 1;
		}
		return dp[i][j];
	};

	return helper(m - 1, n - 1);
};

动态规划-DP table

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
	const m = word1.length;
	const n = word2.length;

	// 初始化动态规划数组，多一行一列用于处理空字符串的情况
	const dp = new Array(m + 1).fill(0).map((i) => new Array(n + 1).fill(0));

	// 初始化边界条件
	for (let i = 1; i <= m; i++) {
		dp[i][0] = i;
	}
	for (let j = 1; j <= n; j++) {
		dp[0][j] = j;
	}

	// 动态规划，计算最小编辑距离
	for (let i = 1; i <= m; i++) {
		for (let 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] = Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;
			}
		}
	}
	return dp[m][n];
};

相关题目

题号	标题	题解	标签	难度
161	相隔为 1 的编辑距离 🔒		双指针 字符串
583	两个字符串的删除操作	[✓]	字符串 动态规划
712	两个字符串的最小ASCII删除和	[✓]	字符串 动态规划
1035	不相交的线		数组 动态规划
2209	用地毯覆盖后的最少白色砖块		字符串 动态规划 前缀和