当前位置：首页 > article >正文

LeetCode 583. 两个字符串的删除操作 java题解

article 2024/12/23 22:44:55

https://leetcode.cn/problems/delete-operation-for-two-strings/
用最长公共子序列的做法。先求出他两的最长公共子序列，这部分是要保留的。字符串中除了这部分的字符，其他字符都需要删除。

class Solution {
    public int minDistance(String word1, String word2) {
        int len1=word1.length(),len2=word2.length();
        int[][] dp=new int[len1+1][len2+1];
        //求最长公共子序列的长度
        //dp[i][j]: i个，j个.初始化为0
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                char c1=word1.charAt(i-1);
                char c2=word2.charAt(j-1);
                if(c1==c2){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return len1+len2-2*dp[len1][len2];
    }
}

你知道的，我只会做最长公共子序列。所以想到了这种歹毒的方法。

下面是别人题解的方法。
dp数组中存储需要删除的字符个数。如果当前字符相同，不用删了，删除个数用上一个状态的。如果当前字符不同，要考虑3种情况：删第一个字符串的，删第二个字符串的，两个都删。

// dp数组中存储需要删除的字符个数
class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i;
        for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j;
        
        for (int i = 1; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,
                                        Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        
        return dp[word1.length()][word2.length()];
    }
}