当前位置：首页 > article >正文

LeetCode题练习与总结：两个字符串的删除操作--583

article 2025/1/27 13:35:40

一、题目描述

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2:

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

二、解题思路

这个问题是经典的编辑距离问题，通常通过动态规划来解决。动态规划的思想是将大问题分解为小问题，并保存小问题的解，以避免重复计算。

解题思路如下：

创建一个二维数组 dp，其中 dp[i][j] 表示使 word1 的前 i 个字符和 word2 的前 j 个字符相同所需的最小步数。
初始化数组，dp[0][j] 表示 word1 为空，变为 word2 的前 j 个字符需要的步数，即 j；同理，dp[i][0] 表示 word2 为空，变为 word1 的前 i 个字符需要的步数，即 i。
遍历两个字符串，对于每一个字符，检查以下三种操作：
- 如果当前字符相同，不需要操作，dp[i][j] = dp[i-1][j-1]。
- 如果当前字符不同，可以选择删除 word1 的当前字符，或者删除 word2 的当前字符，取这两种操作的最小值加一，即 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1。
最终 dp[m][n] 即为结果，其中 m 是 word1 的长度，n 是 word2 的长度。

三、具体代码

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        // 初始化 dp 数组
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // 动态规划填表
        for (int i = 1; i <= m; i++) {
            for (int 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 - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        return dp[m][n];
    }
}

这段代码首先初始化了 dp 数组，然后通过嵌套循环填充了 dp 数组，最后返回了 dp[m][n] 作为结果。

四、时间复杂度和空间复杂度

1. 时间复杂度

初始化 dp 数组：
- 外层循环 i 从 0 到 m（m 是 word1 的长度），内层循环 j 从 0 到 1，这部分的复杂度是 O(m)。
- 外层循环 j 从 0 到 n（n 是 word2 的长度），内层循环 i 从 0 到 1，这部分的复杂度是 O(n)。
填充 dp 数组：
- 外层循环 i 从 1 到 m，内层循环 j 从 1 到 n，每次循环中进行了常数时间的操作（比较字符和取最小值），这部分的复杂度是 O(m * n)。

综上所述，初始化 dp 数组的时间复杂度是 O(m + n)，填充 dp 数组的时间复杂度是 O(m * n)。因为 O(m * n) 是主导项，所以总的时间复杂度是 O(m * n)。

2. 空间复杂度

dp 数组：
- dp 是一个二维数组，大小为 (m + 1) * (n + 1)，因此它占用的空间是 O(m * n)。
其他变量：
- 除了 dp 数组之外，代码中只使用了几个基本类型的变量（m, n, i, j），这些变量占用的空间是常数，即 O(1)。

因此，总的空间复杂度主要取决于 dp 数组，即 O(m * n)。

五、总结知识点

字符串操作：
- 使用 String.length() 方法获取字符串的长度。
- 使用 String.charAt(int index) 方法访问字符串中的单个字符。
数组操作：
- 声明并初始化二维数组 int[][] dp，用于存储动态规划的状态。
动态规划：
- 动态规划是一种算法思想，用于解决具有重叠子问题和最优子结构性质的问题。
- dp[i][j] 表示使 word1 的前 i 个字符和 word2 的前 j 个字符相同所需的最小步数。
边界条件初始化：
- 初始化 dp 数组的边界条件，即当其中一个字符串为空时，将另一个字符串的字符全部删除所需的步数。
状态转移方程：
- 如果 word1 和 word2 当前位置的字符相同，则 dp[i][j] = dp[i - 1][j - 1]。
- 如果字符不同，则 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1，表示在删除一个字符后，取两种操作（删除 word1 的字符或删除 word2 的字符）中的最小值，并加一。
数学运算：
- 使用 Math.min(int a, int b) 方法计算两个整数中的最小值。
循环结构：
- 使用嵌套的 for 循环遍历 word1 和 word2 的所有字符组合。
问题建模：
- 将问题建模为编辑距离问题，并使用动态规划进行求解，这是算法设计中的一种重要技巧。