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

https://leetcode.cn/problems/delete-operation-for-two-strings/solutions/

两种做法,1.直接dp 2.转换题意,思考成LCS

class Solution {
    public int minDistance(String word1, String word2) {
        // 编辑距离的简化版
        // f[i][j]表示word1前i个字符中选择,word2前j个字符中选择得到相同的最小步数
        // 以word1[i],word2[j]是否相同来划分子集
        // 相同意味着这个两个字符都不需要被删除,无需操作,则考虑之前的
        // 不同意味着考虑删除一个字符,但是选择删word1[i]还是word2[j],来划分子集

        // f[i][j] = if(word1[i]==word2[j]) f[i-1][j-1]
        //           else Math.min(f[i-1][j],f[i][j-1])+1
        // 初始化根据f定义,f[1~n][0]=1~n,f[0][1~n]=1~n,即有多少删多少,删成空串
        int[][] f=new int[510][510];
        for(int i=1;i<=word1.length();i++)f[i][0]=i;
        for(int i=1;i<=word2.length();i++)f[0][i]=i;
        for(int i=1;i<=word1.length();i++)
            for(int j=1;j<=word2.length();j++)
            {
                if(word1.charAt(i-1)==word2.charAt(j-1))f[i][j]=f[i-1][j-1];
                else f[i][j]=Math.min(f[i-1][j],f[i][j-1])+1;
            }
        return f[word1.length()][word2.length()];
    }
}

class Solution {
    public int minDistance(String word1, String word2) {
        // 编辑距离的简化版,考虑使用最长公共子序列做
        // 题意等同于word1,word2都是最长公共子序列时拥有最大的长度,因此步数是最小的
        // 答案是:abs(word1.length-LCS)+abs(word2.length-LCS)
        // 
        int[][] f=new int[510][510];
        // f[0~1][0~1]全都无需初始化,因为对应f定义就是0
        for(int i=1;i<=word1.length();i++)
        {
            for(int j=1;j<=word2.length();j++)
            {
                if(word1.charAt(i-1)==word2.charAt(j-1))f[i][j]=f[i-1][j-1]+1;
                else f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
            }
        }
        int LCS=f[word1.length()][word2.length()];
        return Math.abs(word1.length()-LCS)+Math.abs(word2.length()-LCS);
    }
}