72. Edit Distance

72. Edit Distanceopen in new window

🔴 🔖 字符串 动态规划 🔗 LeetCodeopen in new window

题目

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 继续对比；
最后调用递归函数即可。

思路二：动态规划-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 数组会偏移一位。

动态规划数组的大小为 (m+1) * (n+1)，因此时间复杂度为 O(mn) 空间复杂度也为 O(mn)。

代码

动态规划-递归

/**
 * @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];
};

72. Edit Distance

# 72. Edit Distanceopen in new window

# 题目

# 题目大意

# 解题思路

# 思路一：动态规划-递归

# 思路二：动态规划-DP table

# 代码

# 相关题目

72. Edit Distanceopen in new window

题目

题目大意

解题思路

思路一：动态规划-递归

思路二：动态规划-DP table

代码

相关题目