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

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

解题思路

• 计算两个字符串的最小删除操作等价于 计算两个字符串的最大公共子序列
• 通过dp计算两个字符串的最大公共子序列 然后减去

class Solution {
    int[][] memo;
    public int minDistance(String word1, String word2) {
        // 计算两个字符串的最小删除操作等价于 计算两个字符串的最大公共子序列

        int m = word1.length();
        int n = word2.length();

        memo = new int[m + 1][n + 1];

        return m + n  - dp(word1,word2,m,n) * 2;
    }
    
    int dp(String s1,String s2,int m,int n){
        if(m < 0 || n < 0){
            return 0;
        }

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s1.charAt(i  -1) == s2.charAt(j - 1)){
                    // 遇到相同的字符 
                    memo[i][j] = memo[i - 1][j - 1] + 1;
                }else{
                    memo[i][j] = Math.max(memo[i][j - 1],memo[i - 1][j]);
                }
            }
        }

        return memo[m][n];
    }
}