原文链接: https://leetcode-cn.com/problems/delete-operation-for-two-strings
英文原文
Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.
In one step, you can delete exactly one character in either string.
Example 1:
Input: word1 = "sea", word2 = "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Example 2:
Input: word1 = "leetcode", word2 = "etco" Output: 4
Constraints:
1 <= word1.length, word2.length <= 500word1andword2consist of only lowercase English letters.
中文题目
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例：
输入: "sea", "eat" 输出: 2 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
提示：
- 给定单词的长度不超过500。
- 给定单词中的字符只含有小写字母。
通过代码
高赞题解
转换为 LCS 问题
首先，给定两字符 s1 和 s2，求经过多少次删除操作，可使得两个相等字符串。
该问题等价于求解两字符的「最长公共子序列」，若两者长度分别为 $n$ 和 $m$，而最长公共子序列长度为 $max$，则 $n - max + m - max$ 即为答案。
对「最长公共子序列（LCS）」不熟悉的同学，可以看 (题解) 1143. 最长公共子序列。
$f[i][j]$ 代表考虑 $s1$ 的前 $i$ 个字符、考虑 $s2$ 的前 $j$ 个字符（但最长公共子序列中不一定包含 $s1[i]$ 或者 $s2[j]$）时形成的「最长公共子序列（LCS）」长度。
当有了「状态定义」之后，基本上「转移方程」就是呼之欲出：
s1[i]==s2[j]: $f[i][j]=f[i-1][j-1]+1$。代表 必然使用 $s1[i]$ 与 $s2[j]$ 时 LCS 的长度。s1[i]!=s2[j]: $f[i][j]=max(f[i-1][j], f[i][j-1])$。代表 必然不使用 $s1[i]$（但可能使用$s2[j]$）时 和 必然不使用 $s2[j]$（但可能使用$s1[i]$）时 LCS 的长度。
可以发现，上述两种讨论已经包含了「不使用 $s1[i]$ 和 $s2[j]$」、「仅使用 $s1[i]$」、「仅使用 $s2[j]$」和「使用 $s1[i]$ 和 $s2[j]$」四种情况。
虽然「不使用 $s1[i]$ 和 $s2[j]$」会被 $f[i - 1][j]$ 和 $f[i][j - 1]$ 重复包含，但对于求最值问题，重复比较并不想影响答案正确性。
因此最终的 $f[i][j]$ 为上述两种讨论中的最大值。
一些编码细节：
通常会习惯性往字符串头部追加一个空格，以减少边界判断（使下标从 1 开始，并很容易构造出可滚动的「有效值」）。但实现上，不用真的往字符串中最佳空格，只需在初始化动规值时假定存在首部空格，以及对最后的 LCS 长度进行减一操作即可。
代码：
[]class Solution { public int minDistance(String s1, String s2) { char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray(); int n = s1.length(), m = s2.length(); int[][] f = new int[n + 1][m + 1]; // 假定存在哨兵空格，初始化 f[0][x] 和 f[x][0] for (int i = 0; i <= n; i++) f[i][0] = 1; for (int j = 0; j <= m; j++) f[0][j] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]); if (cs1[i - 1] == cs2[j - 1]) f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1); } } int max = f[n][m] - 1; // 减去哨兵空格 return n - max + m - max; } }
- 时间复杂度：$O(n * m)$
- 空间复杂度：$O(n * m)$
序列 DP
上述解决方案是套用了「最长公共子序列（LCS）」进行求解，最后再根据 LCS 长度计算答案。
而更加契合题意的状态定义是根据「最长公共子序列（LCS）」的原始状态定义进行微调：定义 $f[i][j]$ 代表考虑 $s1$ 的前 $i$ 个字符、考虑 $s2$ 的前 $j$ 个字符（最终字符串不一定包含 $s1[i]$ 或 $s2[j]$）时形成相同字符串的最小删除次数。
同理，不失一般性的考虑 $f[i][j]$ 该如何计算：
s1[i]==s2[j]：$f[i][j] = f[i - 1][j - 1]$，代表可以不用必然删掉 $s1[i]$ 和 $s2[j]$ 形成相同字符串；s1[i]!=s2[j]：$f[i][j] = \min(f[i - 1][j] + 1, f[i][j - 1] + 1)$，代表至少一个删除 $s1[i]$ 和 $s2[j]$ 中的其中一个。
$f[i][j]$ 为上述方案中的最小值，最终答案为 $f[n][m]$。
代码：
[]class Solution { public int minDistance(String s1, String s2) { char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray(); int n = s1.length(), m = s2.length(); int[][] f = new int[n + 1][m + 1]; for (int i = 0; i <= n; i++) f[i][0] = i; for (int j = 0; j <= m; j++) f[0][j] = j; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1); if (cs1[i - 1] == cs2[j - 1]) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]); } } return f[n][m]; } }
- 时间复杂度：$O(n * m)$
- 空间复杂度：$O(n * m)$
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 54725 | 87717 | 62.4% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 编辑距离 | 困难 |
| 两个字符串的最小ASCII删除和 | 中等 |
