两个字符串上的删除操作

问题：给你两个单词word1和word2，请问至少需要几次删除操作使得word1和word2变得一样？每一步你都可以从word1或者word2里删除一个字符。

例如，如果输入两个单词"sea"和"eat"，我们至少需要两步删除操作，分别删除第一个单词的's'和第二个单词的't'，使得它们变成相同的"ea"。

分析：

这是LeetCode的第583题。

如果我们熟悉经典的动态规划问题最长公共子串（LCS, Longest Common Subsequence），那么这个问题实际上是最长公共字串的应用。我们的目标是删除一些字符之后，word1和word2相同，也就是剩下的是两个字符串的公共子串。剩下的公共子串越长，那么需要的删除操作就越少。

于是，我们可以写出如下的函数：

接下来我们来解决其中的关键问题，也就是如果求两个字符串的最长公共子串。

解法一：空间效率O(n^2)

由于这是一个求解最优解的问题（“最长”公共子串），我们可以尝试应用动态规划。应用动态规划的第一步找出状态转移函数。我们用函数f(i,j)表示第一个字符串s1的前i个字符组成的子字符串和第二个字符串s2的前j个字符组成的子字符串的最长公共子串的长度。

我们分两种情况讨论这个函数：

1. 如果s1中的第i个字符和s2中的第j个字符相同，f(i,j)等于f(i-1,j-1)+1。这相当于在s1的前i-1个字符组成的子字符串和s2的前j-1个字符组成的子字符串的最长公共子串的基础上增加了一个公共的字符。

2. 如果s1中的第i个字符和s2中的第j个字符不同，f(i,j)等于f(i-1,j)和f(i,j-1)的较大值。既然s1中的第i个字符和s2中的第j个字符不同，我们可以忽略s1中的第i个字符，去看看在s1的前i-1个字符组成的子字符串和s2的前j个字符组成的子字符串的最长公共子串的长度，这就是f(i-1,j)的值。同样，我们也可以忽略s2中的第j个字符，去看看在s1的前i个字符组成的子字符串和s2的前j-1个字符组成的子字符串的最长公共子串的长度，这就是f(i,j-1)的值。

由于状态转移函数有两个变量i和j，我们可以用一个二维矩阵来存储f(i,j)的值。以下就是基于二维矩阵的代码：

如果两个字符串的长度分别是m和n，上述代码的时间和空间复杂度都是O(mn)。

解法二：空间效率O(n)

仔细分析上述代码，我们就能发现在求解dp[i][j]的时候只用到了dp[i-1][j-i]、dp[i-1][j]和dp[i][j-1]，这三个值要么位于二维矩阵dp的第i-1行，要么位于dp的第i行。因此，求任意一个dp[i][j]的时候，只要矩阵中的第i-1行和第i行这两行就够了，并不是真正需要保留所有的m+1行（假设m为第一个字符串s1的长度）。这样空间复杂度就降低到O(n)了。

接下来我们看能不能进一步减少空间的使用，只保留二维矩阵dp中的一行，也就是只保留一个一维数组。如果只保留二维矩阵中的一行，第i-1行第j-1的数值（即f(i-1,j-1)）和第i行j-1列的数值（即f(i,j-1)）都对应到一维数组中的第j-1个数值。可是我们在求f(i,j)又同时需要第i-1行第j-1列的数值和第i行j-1列的数值，因此我们需要确保它们两个在使用之前不能相互覆盖。

我们注意到f(i-1,j-1)的值只是在求解f(i,j)有用，之后再也不需要。因此我们在求解f(i,j)的时候，先不把f(i,j-1)的值写入到一维数组，而是用一个临时变量保存。在求解f(i,j)之后，再把f(i,j-1)写入到一维数组。此时即使把f(i-1,j-1)的值覆盖，也不会有任何问题。

基于上面的优化，我们可以写出如下代码：

上述代码仍然需要两重循环，因此时间复杂度仍然是O(mn)。由于只需要一个一维数组，因此空间复杂度是O(n)。

举一反三：

给我们两个字符串s1和s2，请问如何删除字符使得两个字符串相同，并且被删除的字符的ASCII值的和最小？求被删除的字符的ASCII值的和的最小值。

这是LeetCode的第712题。

这实际上前面问题的变种。我们如果能求出ASCII值最大的公共字串，那么其他的就是被删除的ASCII值的和最小的字符。因此我们我们只需要在前面代码的基础上稍微改改，就能解决这个问题。

参考代码如下：