【LeetCode583】两个字符串的删除操作

题目

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

示例：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-operation-for-two-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

class Solution {
    public int minDistance(String word1, String word2) {
/*思路分析： 这是典型的字符串操作最优题，一般动态规划非常有效。下面是状态转移方程的建立：
dp[i][j]表示的word1的前i个字符与word2的前j个字符达到相同所需的最小步数
要使word1的前i个字符与word2的前j个字符，可以有三种方法：

第一种：dp[i - 1][j - 1] 如果word1[i - 1] == word2[j - 1]相等，则先使word1的前i - 1个字符转化为word2的前j - 1个字符，然后自动匹配
第二种：dp[i - 1][j] + 1代表将word1的前i - 1个字符转换为word2的前j个字符，然后删除word1中的第i个字符
第三种：dp[i][j - 1] + 1代表将word1的前i个字符转换为word2的前j - 1个字符，然后删除word2中的第j个字符
状态转移方程：dp[i][j] = min(dp[i][j], min(dp[i - 1][j], dp[i][j - 1]) + 1);
*/
        int m = word1.length();
        int n = word2.length();

        //dp[i][j]表示word1[0...i - 1]与word2[0...j-1]的最大公共子序列长度
        int[][] dp = new int[m + 1][n + 1];

        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] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        //m+n - 2*(dp[m][n])表示需要删除的个数
        return m + n - 2 * dp[m][n];


    }
}