百度地图 企业网站,给wordpress公告,产品宣传类网站设计注意,3d动画制作设计公司392.判断子序列
给定字符串 s 和 t #xff0c;判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些#xff08;也可以不删除#xff09;字符而不改变剩余字符相对位置形成的新字符串。#xff08;例如#xff0c;ace是abcde的…392.判断子序列
给定字符串 s 和 t 判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。 其实就是最长公共子序列的变种题如果公共子序列长度等于s那么返回true public boolean isSubsequence(String s, String t) {int length1 s.length(); int length2 t.length();int[][] dp new int[length11][length21];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;}}
}
还可以用双指针效率其实更高时间复杂度为 ON
class Solution {public boolean isSubsequence(String s, String t) {int i 0, j 0;while(i s.length() j t.length()){if(s.charAt(i) t.charAt(j)) i;j;}return i s.length();}
} 115.不同的子序列 参考代码随想录
1. dp数组dp table以及下标的含义
dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
2. 递推公式
这一类问题基本是要分析两种情况
s[i - 1] 与 t[j - 1]相等s[i - 1] 与 t[j - 1] 不相等
当s[i - 1] 与 t[j - 1]相等时dp[i][j]可以有两部分组成。
一部分是用s[i - 1]来匹配那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母所以只需要 dp[i-1][j-1]。
一部分是不用s[i - 1]来匹配个数为dp[i - 1][j]。
例如 sbagg 和 tbag s[3] 和 t[2]是相同的但是字符串s也可以不用s[3]来匹配即用s[0]s[1]s[2]组成的bag。
当然也可以用s[3]来匹配即s[0]s[1]s[3]组成的bag。
所以当s[i - 1] 与 t[j - 1]相等时dp[i][j] dp[i - 1][j - 1] dp[i - 1][j];
当s[i - 1] 与 t[j - 1]不相等时dp[i][j]只有一部分组成不用s[i - 1]来匹配就是模拟在s中删除这个元素即dp[i - 1][j]
所以递推公式为dp[i][j] dp[i - 1][j];
为什么只考虑 “不用s[i - 1]来匹配” 这种情况 不考虑 “不用t[j - 1]来匹配” 的情况呢。
这里大家要明确我们求的是 s 中有多少个 t而不是 求t中有多少个s所以只考虑 s中删除元素的情况即 不用s[i - 1]来匹配 的情况。
3. 初始化
从递推公式dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]; 和 dp[i][j] dp[i - 1][j]; 中可以看出dp[i][j] 是从上方和左上方推导而来如图那么 dp[i][0] 和dp[0][j]是一定要初始化的。 dp[i][0] 表示以i-1为结尾的s可以随便删除元素出现空字符串的个数。
那么dp[i][0]一定都是1因为也就是把以i-1为结尾的s删除所有元素出现空字符串的个数就是1。
再来看dp[0][j]dp[0][j]空字符串s可以随便删除元素出现以j-1为结尾的字符串t的个数。
那么dp[0][j]一定都是0s如论如何也变成不了t。 4. 遍历顺序
从递推公式dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]; 和 dp[i][j] dp[i - 1][j]; 中可以看出dp[i][j]都是根据左上方和正上方推出来的。
所以遍历的时候一定是从上到下从左到右这样保证dp[i][j]可以根据之前计算出来的数值进行计算。
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()];}
}
