代码随想录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()];}

小结

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。