[数据结构与算法]编辑距离题目总结

判断子序列

class Solution {
    public boolean isSubsequence(String s, String t) {
        //dp定义:dp[i][j]为到i-1,j-1最长子序列的长度
        //递推:相等,dp[i][j] = dp[i-1][j-1] + 1;
        //不相等,dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
        int[][] dp = new int[s.length()+1][t.length()+1];
        for(int i = 1;i <= s.length();i++) {
            for(int j = 1;j <= t.length();j++) {
                if(s.charAt(i-1) == t.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]);
                }
            }
        }
        if(dp[s.length()][t.length()] != s.length()) {
            return false;
        }
        return true;
    }
}

不同的子序列
这道题虽然也是删除,但是它和上一道题还不大一样,就是当字符相等的时候,我可以选择用当前字符匹配,也可以选择不用,用的话就是i+1到最后包含j+1到最后,不用就是i+1到最后,j到最后因为当前j不用嘛.时刻记住dp的定义.

class Solution {
    public int numDistinct(String s, String t) {
        //dp数组定义:dp[i][j]表示s[i]到之后包含t[j]到最后的个数
        int[][] dp = new int[s.length()+1][t.length()+1];
        if(s.length() < t.length()) return 0;
        for(int i = 0;i <= s.length();i++) {
            dp[i][t.length()] = 1;
        }
        for(int i = s.length() - 1;i >= 0;i--) {
            char sc = s.charAt(i);
            for(int j = t.length() - 1;j >= 0;j--) {
                char tc = t.charAt(j);
                if(sc == tc) {
                    dp[i][j] = dp[i+1][j+1] + dp[i+1][j];
                }else {
                    dp[i][j] = dp[i+1][j];
                }
            }
        }
        return dp[0][0];
    }
}

两个字符串的删除操作
可以借鉴前几题写一个间接的写法,也能直接写,直接写的话就是递推公式有点变化.

class Solution {
    public int minDistance(String word1, String word2) {
        //这道题本质就是找word1,word2的相同子序列的长度,然后两个中短的一减就行了
        //dp定义:dp[i][j]表示i到后和j到后子序列的长度
        //递推:word1[i] == word2[j]时,dp[i][j] = dp[i+1][j+1] + 1;
        //不一样,dp[i][j] = Math.max(dp[i+1][j],dp[i][j+1]);
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for(int i = word1.length() - 1;i >= 0;i--) {
            char w1 = word1.charAt(i);
            for(int j = word2.length() - 1;j >= 0;j--) {
                char w2 = word2.charAt(j);
                if(w1 == w2) {
                    dp[i][j] = dp[i+1][j+1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j+1]);
                }
            }
        }
        return word1.length() + word2.length() - dp[0][0] * 2;
    }
}

编辑距离
如果想不到用dp的话,这道题容易让人一头雾水,感觉情况很多理不清.但其实它用动规就很清楚了,就是考虑当前两个字符相等的情况,不相等的情况各对应的操作即可,相同不操作,不相同,就是删增替,值得注意的是,word1增就等价于word2减,二者操作数是相同的.

class Solution {
    public int minDistance(String word1, String word2) {
        //dp[i][j]表示以下标i-1的word1,到下标j-1的word2,最短编辑距离
        //递推:word1[i]==word2[j] dp[i][j] = dp[i-1][j-1];
        //word1[i]!=word2[j],有三种情况,删增替
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for(int i = 1;i <= word1.length();i++) dp[i][0] = i;
        for(int j = 1;j <= word2.length();j++) dp[0][j] = j;
        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)) {
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = Math.min(dp[i-1][j] + 1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+1));
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

总之就是dp的定义时刻要牢记,然后分情况写就行了.