583. 两个字符串的删除操作

给定两个单词 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[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度，遍历 s1 和 s2 的每个字符， 填充 dp 数组，如果字符相同，当前字符属于 LCS，长度加一，如果字符不同，取舍一个字符后求最大 LCS 长度。 最小删除次数 = 字符串 s1 的长度 - LCS 长度 + 字符串 s2 的长度 - LCS 长度。类似72.编辑距离

class Solution {
    // 计算将字符串 s1 转换为字符串 s2 所需的最少操作数
    public int minDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        // 复用前文计算最长公共子序列（LCS）长度的函数
        int lcs = longestCommonSubsequence(s1, s2);
        // 最小删除次数 = 字符串 s1 的长度 - LCS 长度 + 字符串 s2 的长度 - LCS 长度
        return m - lcs + n - lcs;
    }

    // 计算字符串 s1 和 s2 的最长公共子序列（LCS）的长度
    int longestCommonSubsequence(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        // 定义 dp 数组，dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度
        int[][] dp = new int[m + 1][n + 1];

        // 遍历 s1 和 s2 的每个字符，填充 dp 数组。因为i=0或j=0时dp[i][j]都是0，所以从1开始处理。
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 注意：i 和 j 是个数，所以要减一
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    // 如果字符相同，当前字符属于 LCS，长度加一
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    // 如果字符不同，取舍一个字符后求最大 LCS 长度。
                    // 注意如果是公共子串，则这里是0，因为不连续了。
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        
        // dp[m][n] 储存着整个 s1 和 s2 的 LCS 长度
        return dp[m][n];
    }
}

• 时间复杂度: $O(m n)$ ，其中 $m$ 和 $n$ 分别是字符串 $\operatorname{word}_1$ 和 $\operatorname{word}_2$ 的长度。二维数组 $d p$ 有 $m+1$ 行和 $n+1$ 列，需要对 $d p$ 中的每个元素进行计算。
• 空间复杂度： $O(m n)$ ，其中 $m$ 和 $n$ 分别是字符串 $\operatorname{word}_1$ 和 $\operatorname{word}_2$ 的长度。创建了 $m+1$ 行 $n+1$ 列的二维数组 $d p$ 。

动态规划-直接算最小步数

dp[i][j] 表示 word1[0..i-1] 和 word2[0..j-1] 的最小编辑距离，word2 为空字符串时，将 word1 的所有字符删除即可，word1 为空字符串时，将 word2 的所有字符插入即可，正序遍历i和j，如果当前字符相等，不需要任何操作，继承之前的结果，否则考虑删除word1或word2操作，取其中的最小值加一

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        // 定义 dp 数组，其中 dp[i][j] 表示 word1[0..i-1] 和 word2[0..j-1] 的最小编辑距离
        int[][] dp = new int[m + 1][n + 1];
        
        // 初始化 base case：word2 为空字符串时，将 word1 的所有字符删除即可
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        // 初始化 base case：word1 为空字符串时，将 word2 的所有字符插入即可
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        
        // 自底向上计算 dp 数组的值
        for (int i = 1; i <= m; i++) {
            char c1 = word1.charAt(i - 1);  // 取 word1 的第 i 个字符
            for (int j = 1; j <= n; j++) {
                char c2 = word2.charAt(j - 1);  // 取 word2 的第 j 个字符
                
                // 如果当前字符相等，不需要任何操作，继承之前的结果
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 如果字符不等，考虑每个字符串的删除操作，取其中的最小值加一
                    // 《编辑距离》问题中允许的操作是插入、删除、替换，这里只允许删除。
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        
        // dp[m][n] 储存着 word1 和 word2 的最小编辑距离
        return dp[m][n];
    }
}

• 时间复杂度: $O(m n)$ ，其中 $m$ 和 $n$ 分别是字符串 $\operatorname{word}_1$ 和 $\operatorname{word}_2$ 的长度。二维数组 $d p$ 有 $m+1$ 行和 $n+1$ 列，需要对 $d p$ 中的每个元素进行计算。
• 空间复杂度： $O(m n)$ ，其中 $m$ 和 $n$ 分别是字符串 $\operatorname{word}_1$ 和 $\operatorname{word}_2$ 的长度。创建了 $m+1$ 行 $n+1$ 列的二维数组 $d p$ 。

滚动更新

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        
        // 定义滚动数组，只需要一维数组来存储当前行和上一行的数据
        int[] dp = new int[n + 1];
        
        // 初始化 base case：word1 为空字符串时，将 word2 的所有字符插入即可
        for (int j = 1; j <= n; j++) {
            dp[j] = j;
        }
        
        // 自底向上计算 dp 数组的值
        for (int i = 1; i <= m; i++) {
            // 保存更新前的dp[0]，只有计算dp[1]时要用到。
            int prev = dp[0];
            dp[0] = i; // 更新dp[0]，当前行的第一个元素，表示将 word1 的所有字符删除即可。因为下面会进行j-1，所以把j=0单独拿出来。dp[0]和dp[j]一样，更新前都要先保存原值。
            
            for (int j = 1; j <= n; j++) {
                // 保存更新前的 dp[j] 的值，相当于dp[i-1][j]，下一轮要用，对下一轮j循环相当于dp[i-1][j-1]
                int temp = dp[j];
                char c1 = word1.charAt(i - 1);  // 取 word1 的第 i 个字符
                char c2 = word2.charAt(j - 1);  // 取 word2 的第 j 个字符
                
                // 如果当前字符相等，不需要任何操作，继承之前的结果
                if (c1 == c2) {
                    dp[j] = prev;
                } else {
                    // 如果字符不等，考虑删除或插入操作，取其中的最小值加一
                    dp[j] = Math.min(dp[j], dp[j - 1]) + 1;
                }
                
                prev = temp; // 更新 prev 为当前 dp[j] 的值
            }
        }
        
        // dp[n] 储存着 word1 和 word2 的最小编辑距离
        return dp[n];
    }
}

滚动更新，两个一维数组

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        
        // 定义两个一维数组，prevRow 表示上一行，currentRow 表示当前行
        int[] prevRow = new int[n + 1];
        int[] currentRow = new int[n + 1];

        // 初始化 base case：word1 为空字符串时，插入所有 word2 的字符
        for (int j = 1; j <= n; j++) {
            prevRow[j] = j;
        }

        // 自底向上计算 currentRow 数组的值
        for (int i = 1; i <= m; i++) {
            char c1 = word1.charAt(i - 1);  // 取 word1 的第 i 个字符
            currentRow[0] = i;  // j=0，即当 word2 为空时，需要删除 word1 中的所有字符
            
            for (int j = 1; j <= n; j++) {
                char c2 = word2.charAt(j - 1);  // 取 word2 的第 j 个字符
                
                if (c1 == c2) {
                    // 如果字符相等，继承上次的结果
                    currentRow[j] = prevRow[j - 1];
                } else {
                    // 如果字符不等，考虑删除操作，取最小值加一
                    currentRow[j] = Math.min(prevRow[j], currentRow[j - 1]) + 1;
                }
            }
            
            // 更新 prevRow，准备处理下一行，把currentRow赋给prevRow
            System.arraycopy(currentRow, 0, prevRow, 0, n + 1);
        }
        
        // prevRow[n] 储存着 word1 和 word2 的最小编辑距离
        return prevRow[n];
    }
}