LeetCode 583. 两个字符串的删除操作    原题链接    中等

作者： 作者的头像   wzc1995 ,  2018-07-29 00:41:28 ,  所有人可见 ,  阅读 1417

2


题目描述

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任一字符串的一个字符。

样例

输入："sea", "eat"
输出：2
解释：第一步将 "sea" 变为 "ea"，第二步将 "eat" 变为 "ea"。

限制

  • 给定单词的长度不超过 500。
  • 给定单词中的字符只含有小写字母。

算法

(动态规划) $O(nm)$

此题类似于求最长公共子序列(LCS)。

  1. 设计状态 $f(i, j)$ 表示 word1 的前 $i$ 个字母和 word2 的前 $j$ 个字母相同所需的最少步数。
  2. 转移时，若 word1 的第 $i$ 个字母和 word2 的第 $j$ 个字母相同，则 $f(i, j) = f(i - 1, j - 1)$。否则，$f(i, j) = \min (f(i - 1, j), f(i, j - 1)) + 1$。
  3. 初始时，$f(i, 0) = i, f(0, j) = j$；最终答案为 $f(n, m)$。

时间复杂度

  • 状态数为 $O(nm)$，转移数为 $O(1)$，故总时间复杂度为 $O(nm)$。

C++ 代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length(), m = word2.length();
        vector<vector<int>> f(n + 1, vector<int>(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++) {
                if (word1[i - 1] == word2[j - 1])
                    f[i][j] = f[i - 1][j - 1];
                else
                    f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
            }

        return f[n][m];
    }
};

17 评论

用户头像
天空会变灰色   2023-03-06 12:41         踩      回复

这里不用word1=' '+word1吗，有点分不清何字符串时应该加入空格，何时应该下标错位了（晕

用户头像
wzc1995   2023-03-06 14:06         踩      回复

这个随意，没有固定套路，保证下标正确就行

用户头像
Java   2021-07-05 23:57         踩      回复

f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
f[i][j] = min(f[i][j], f[i - 1][j - 1] + word1[i] == word2[j] ? 0 : 2);
这么算为啥不行。

用户头像
wzc1995   2021-07-07 21:33         踩      回复

可以的，没问题

用户头像
wzc1995   2021-07-07 21:34    回复了 wzc1995 的评论         踩      回复

只不过不相等的时候那个 +2 的转移其实可以省略

用户头像
Java   2021-07-07 23:32    回复了 wzc1995 的评论         踩      回复

class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.size(), m = word2.size();
int f[n + 1][m + 1];
word1 = ‘ ‘ + word1, word2 = ‘ ‘ + word2;
memset(f, 0x3f, sizeof f);

    for(int i = 0; i <= n; i ++ ) f[i][0] = i;
    for(int i = 0; i <= m; i ++ ) f[0][i] = i;

    for(int i = 1; i <= n; i ++ ) 
        for(int j = 1; j <= m; j ++ ) 
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + word1[i] == word2[j] ? 0 : 2);
        }
    return f[n][m];
}

};

用户头像
Java   2021-07-07 23:32    回复了 wzc1995 的评论         踩      回复

这么写不行，代码贴上来了

用户头像
wzc1995   2021-07-07 23:40    回复了 Java 的评论         踩      回复

word1[i] 改成 word1[i - 1]，下标错位

用户头像
Java   2021-07-08 13:24    回复了 wzc1995 的评论         踩      回复

不用改吧，前面有word1 = ‘ ‘ + word1, word2 = ‘ ‘ + word2，加了空格的。

用户头像
wzc1995   2021-07-09 23:04    回复了 Java 的评论         踩      回复 
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length(), m = word2.length();
        vector<vector<int>> f(n + 1, vector<int>(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] = min(f[i - 1][j], f[i][j - 1]) + 1;
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + (word1[i - 1] == word2[j - 1] ? 0 : 2));
            }

        return f[n][m];
    }
};
用户头像
wzc1995   2021-07-09 23:05    回复了 Java 的评论         踩      回复

int f[n+1][m+1] 这样定义数组在C语法里是未定义行为

用户头像
wzc1995   2021-07-09 23:06    回复了 wzc1995 的评论         踩      回复

可以令 n 和 m 都是 const 常量，或者使用 new 动态分配内存，或者使用 vector 类模板

用户头像
Java   2021-07-11 20:29    回复了 wzc1995 的评论         踩      回复

class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.size(), m = word2.size();
int f[n + 1][m + 1];
word1 = ‘ ‘ + word1, word2 = ‘ ‘ + word2;
memset(f, 0x3f, sizeof f);

我用了memset啊，为啥会是未知的

用户头像
wzc1995   2021-07-12 12:53    回复了 Java 的评论         踩      回复

int f[n + 1][m + 1] 如果 n 和 m 是变量是非法的定义数组的方式

用户头像
Java   2021-07-12 17:07    回复了 wzc1995 的评论         踩      回复 
//改成这样还是不行，感觉就是转移方程有问题
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, INT_MAX));
        word1 = ' ' + word1, word2 = ' ' + word2;

        for(int i = 0; i <= n; i ++ ) f[i][0] = i;
        for(int i = 0; i <= m; i ++ ) f[0][i] = i;

        for(int i = 1; i <= n; i ++ ) 
            for(int j = 1; j <= m; j ++ ) 
            {
                f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                f[i][j] = min(f[i][j], f[i - 1][j - 1] + word1[i] == word2[j] ? 0 : 2);
            }
        return f[n][m];
    }
};
用户头像
wzc1995   2021-07-14 00:10    回复了 Java 的评论         踩      回复

f[i][j] = min(f[i][j], f[i - 1][j - 1] + (word1[i] == word2[j] ? 0 : 2)) 最后的三目运算符要加括号，否则优先级会有问题

用户头像
Java   2021-07-14 13:18    回复了 wzc1995 的评论         踩      回复

谢谢大佬🙏