[数据结构与算法]583. 两个字符串的删除操作

一、题目描述

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

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

示例 1：

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

示例 2：

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

二、解题

动态规划

dp[i][j]：表示要使word1和word2变成下标为i和j时相等的字符串需要最少的删除次数

初始化：

• 当word1字符串为空时，需要将word2字符串依次删除才可以：
  dp[0][j]=j
• 同样的，当word2字符串为空时，需要将word1字符串依次删除才可以：
  dp[i][0]=i
• 当两者都不为空时，从第一个字符开始遍历，要么两个字符相等，要么两个字符不相等：
  • 两个字符相等时，直接与上一个状态相等
    dp[i][j] = dp[i - 1][j - 1]
  • 两个字符不相等时，则由上一个状态转移，找最小的删除次数，然后+1；
    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        //当一个字符串为空时，如果需要两个字符串都相同，必须将另一个字符串全部删除
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        //当一个字符串为空时，如果需要两个字符串都相同，必须将另一个字符串全部删除
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            char c1 = word1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = word2.charAt(j - 1);
                //如果两个字符串的字符相等，则最少删除次数不变。
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //如果两个字符串的字符不相等，则取两个字符串减一个后的最小值 然后+1。
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}