583. 两个字符串的删除操作 - Java 动态规划

原题地址：https://leetcode.cn/problems/delete-operation-for-two-strings

题解

这题实际上是1143. 最长公共子序列 的变种

让两个字符串相等实际上就是在求两个字符串的公共子序列，而最少的步数隐含了要求最长公共子序列的条件

我们直接求出两个字符串的公共子序列，然后看看每个字符串删到这个公共子序列需要经过多少步即可

时间复杂度：O(MN)

空间复杂度：O(MN)

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp=new int[word1.length()+1][word2.length()+1];
        for(int r=1;r<dp.length;r++){
            for(int c=1;c<dp[r].length;c++){
                if(word1.charAt(r-1)==word2.charAt(c-1))
                    dp[r][c]=dp[r-1][c-1]+1;
                else
                    dp[r][c]=Math.max(dp[r][c-1],dp[r-1][c]);
            }
        }
        return word1.length()+word2.length()-2*dp[dp.length-1][dp[0].length-1];
    }
}