代码随想录Day58

392.判断子序列

题目：392. 判断子序列 - 力扣（LeetCode）

思路：定义重合数记录s与t的比对情况，挨个取出t的字符，与s的字符进行比较，如果相同，重合数就加1，跳到s的下一个字符进行比较，最后判断重合数是否为s字符串长度

尝试（暴力AC）

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s.length()==0) return true;
        int count = 0;
        for(int i =0; i<t.length() && count<s.length(); i++){
            if(s.charAt(count) == t.charAt(i)){
                count++;
            }
        }
        return count==s.length();
    }
}

答案

class Solution {
    public boolean isSubsequence(String s, String t) {
        int length1 = s.length(); int length2 = t.length();
        int[][] dp = new int[length1+1][length2+1];
        for(int i = 1; i <= length1; i++){
            for(int j = 1; j <= length2; j++){
                if(s.charAt(i-1) == t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        if(dp[length1][length2] == length1){
            return true;
        }else{
            return false;
        }
    }
}

小结

dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

115.不同的子序列

题目：115. 不同的子序列 - 力扣（LeetCode）

思路：想不到dp数组要如何定义，果断放弃

答案

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i < s.length() + 1; i++) {
            dp[i][0] = 1;
        }
        
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 1; j < t.length() + 1; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        
        return dp[s.length()][t.length()];
    }
}

小结

dp数组定义跟上一道题类似：dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

dp数组的初始化，根据递推公式来看，是从左上角往下推，所以第一行和第一列一定要初始化

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

题目：583. 两个字符串的删除操作 - 力扣（LeetCode）

思路：怎么感觉就是求最长公共子序列

尝试（还是在求最长公共子序列）

class Solution {
    public int minDistance(String word1, String word2) {
        char[] char1 = word1.toCharArray();
        char[] char2 = word2.toCharArray();
        int[][] dp = new int[word1.length()+1][word2.length()+1];
        for(int i=1; i<=word1.length(); i++ ){
            for(int j = 1; j<=word2.length(); j++){
                if(char1[i-1] == char2[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]);
                }
            }
        }
        return word1.length()+word2.length() - 2*dp[word1.length()][word2.length()];
    }
}

答案

// 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()];
    }