0583. Delete Operation for Two Strings
======================================
题目信息
--------
:题号: 0583
:难度: Medium
:主题: 两个字符串、删除字符、相同结果、最少操作
:原题: `LeetCode 0583 `_
:重点: 每次只能从其中一个字符串删除一个字符、不能插入或替换、目标是让两串完全相同
题目重述
--------
给定两个只含小写英文字母的字符串 ``word1`` 和 ``word2``。一次操作可以从任意一个字符串中删除一个字符。
返回使两个字符串最终完全相同所需的最少删除次数。可以从两个字符串都删除字符,但不能插入、替换或改变剩余字符的相对顺序;若两串起初相同,答案为 ``0``。
自建示例
--------
两个字符串都需要删除:
.. code-block:: text
输入:word1 = "abcd",word2 = "ace"
输出:3
解释:从 word1 删除 b、d,从 word2 删除 e,两个字符串都变为 "ac",共删除 3 次。
初始已经相同:
.. code-block:: text
输入:word1 = "tree",word2 = "tree"
输出:0
解释:无需执行任何删除。
保留最长公共子序列
------------------
最终相同的字符串必须同时是两个输入的公共子序列。若保留最长公共子序列长度为 ``l``,删除次数就是 ``len1-l + len2-l``;因此先求 LCS,再从两边删除其余字符即可达到最少操作。
用一维 DP 保存前缀 LCS 长度,当前行从右向左更新,避免覆盖 ``dp[j-1]`` 所代表的左上状态。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int minDistance(std::string word1, std::string word2) {
int n = static_cast(word2.size());
std::vector dp(n + 1, 0);
for (char first : word1) {
int diagonal = 0;
for (int j = 1; j <= n; ++j) {
int old = dp[j];
if (first == word2[j - 1]) {
dp[j] = diagonal + 1;
} else {
dp[j] = std::max(dp[j], dp[j - 1]);
}
diagonal = old;
}
}
return static_cast(word1.size() + word2.size()) -
2 * dp[n];
}
};
代码分析
--------
LCS 状态的匹配与跳过转移覆盖所有共同保留方案,删除非 LCS 字符后即可构造相同结果,故该下界可达。时间复杂度为 ``O(|word1|*|word2|)``,空间复杂度为 ``O(|word2|)``。