目录
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1：
示例 2：
提示：
? ? ? ? 用贪心，遍历两个数组，若相同记录位置继续往下比较
? ? ? ? 看似简单其实写了很久，没有理清楚两个循环的终止 两个变量一个j和一个i
? ? ? ? 若j==length 且 i 未结束，就为false
? ? ? ? 若 j！=length 且i未结束，且 c1[i] = c2[j]则继续 j++
? ? ? ?
????????
? ? ? ? 用动态规划，和之前最长子序列一样的
? ? ? ? (若最长子序列长度和s相等则返回true 否则返回false)
? ? ? ? 确定dp数组和每个下标的含义
? ? ? ??
? ? ? ? dp[i][j]记录末尾为i-1和j-1的最长的子序列的长度
????????
? ? ? ? 确定递推公式
? ? ? ? 要从递推公式来进行考虑
? ? ? ?若text1[i] = text2[j] 则在之前的基础上+1
????????????????dp[i][j] = dp[i-1][j-1]+1;?
????????若text1[i] != text2[j] 则等于之前的最大值?
? ? ? ? ? ? ? ? 之前的最长子序列是dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
? ? ? ? ? ? ? ? 这道题是看t能否组成s ，则只要考虑去掉t[j-1]能组成s的最大长度
?????????????????dp[i][j] =? dp[i][j-1]
???????? dp数组初始化
? ? ? ? ? ? ? ? ? 因为dp[i][j] 代表0~i-1，0~j-1的最大子序列，则不需要定义dp[i][0],dp[0][j]，因为0 代表-1没有意义
? ? ? ? 确定遍历顺序
? ? ? ? 从前往后，从上往下
? ? ? ? 举例推导dp数组? ? ? ? ? ?
? ? ? ? 打印dp数组
? ? ? ? 打印最后一个元素
? ? ? ?自己需要注意i-1和j-1这个点，同时for循环的条件需要 i<=? j<=? 不要忘了等号
? ? ? ? 要结合dp的定义来写递推公式,脑袋转个弯，比如之前是求最长公共子序列，这道题是求t是否能组成s，则也可以视为求两个公共最长子序列，看子序列是否等于s即可
? ? ? ? t是否能组成s ，则若s[i-1]!=t[j-1]时，dp[i][j]要看t[j-2]能组成s[i-1]的最大长度 dp[i][j] = dp[i][j-1]
????????
? ? ? ?
????????字符串用charAt 比较好写，获取目标索引的字符
???????? 不要写成indexOf 那个是获取字符的索引
????????
class Solution {
public boolean isSubsequence(String s, String t) {
//简单办法，贪心 先找第一个，再往后找第二个，再往后找第三个
//卡哥思路 ，看两者最长公共子序列是否相等
//确定dp数组的和下标的含义
//dp[i][j] 代表0~i 和0~j的最长相同公共子序列的长度
//表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]
//确定递推公式
// 若s[i-1]==t[j-1] 则dp[i][j] = dp[i-1][j-1]+1
// 若s[i-1]!=t[j-1] 则dp[i][j] = max(dp[i][j-1],dp[i-1][j])
//dp数组初始化
//不用初始化
//确定遍历顺序
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++){
//charAt 获取指定位置的字符
//indexOf 获取指定字符的索引
if(s.charAt(i-1)==(t.charAt(j-1))){
dp[i][j] = dp[i-1][j-1]+1;
}else{
//卡哥做法，这里不需要max
//s和t进行比较，若不相等，则相当于t要删除元素 s[i-1]和t[j-2]的比较结果
//只需要dp[i][j] = dp[i][j-1];
dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
}
}
}
return dp[s.length()][t.length()]==s.length();
/*char[] c1 = s.toCharArray();
char[] c2 = t.toCharArray();
if(c1.length>c2.length){
return false;
}
int j = 0;
for(int i=0;i<c1.length;i++){
//进入这里之后，我们需要判断是否和第二个数组的值相等，同时要记住之前比较的位置
while(j<c2.length&&c1[i]!=c2[j]){
j++;
}
//若j到了末尾则不存在，直接返回false
if(j==c2.length){
return false;
}
//若两者相等，记录好j的位置，从相等的下一个开始比较
if(c1[i]==c2[j]){
j++;
}
}
return true;*/
}
}给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE"?是?"ABCDE"?的一个子序列，而?"AEC"?不是）
题目数据保证答案符合 32 位带符号整数范围。
? ? ? ?想着用dp 来记录s序列中t出现的个数
? ? ? ? 没想出递推公式来? ? ? ?
????????
? ? ? ? 用动态规划
? ? ? ? (审题，这道题可以理解为字符串s中能组成t的个数)
? ? ? ? 确定dp数组和每个下标的含义
? ? ? ??
? ? ? ? dp[i][j]记录0~i-1的s 能组成多少个0~j-1的t
????????
? ? ? ? 确定递推公式
? ? ? ? 要从递推公式来进行考虑
? ? ? ?若s[i-1] = t[j-1] 则在之前的基础上+dp[i-1][j]
????????????????dp[i][j] = dp[i-1][j-1]+dp[i-1][j];?
? ? ? ? 因为这个题求的时能组成0~j-1的t的个数
? ? ? ? 当前选中的是s[i-1] 则有两种考虑?
???????? 1 若加上s[i-1]? ，也就是dp[i-1][j-1] 的基础上组成 dp[i][j]
? ? ? ? ?2 若不加上s[i-1]，也就是s[i-1] 之前的元素也能组成t[j-1] 则为dp[i-1][j]
? ? ? ? 简而言之 dp[i-1][j] 也是能组成带上t[i-1]这个元素的 t字符串 的
????????若text1[i] != text2[j] 则等于之前的
? ? ? ? ? ? ? ? 之前的最长子序列是dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
? ? ? ? ? ? ? ? 这道题是看s能否组成t，去掉s[i-1]也能组成j的最多个数是多少
?????????????????dp[i][j] =? dp[i-1][j]
???????? dp数组初始化
? ? ? ? ? ?dp[i][0]=1 s组成空串??
? ? ? ? ? ?dp[0][j] =0 空串无法组成t
? ? ? ? ? ?dp[0][0] = 1 空串可以组成空串
? ? ? ? 确定遍历顺序
? ? ? ? 从前往后，从上往下
? ? ? ? 举例推导dp数组? ? ? ? ? ?
? ? ? ? 打印dp数组
? ? ? ? 打印最后一个元素
? ? ? ?自己需要注意i-1和j-1这个点，同时for循环的条件需要 i<=? j<=? 不要忘了等号
? ? ? ? 要结合dp的定义来写递推公式,脑袋转个弯，比如之前是求最长公共子序列，这道题是求t是否能组成s，则也可以视为求两个公共最长子序列，看子序列是否等于s即可
? ? ? ? t是否能组成s ，则若s[i-1]!=t[j-1]时，dp[i][j]要看t[j-2]能组成s[i-1]的最大长度 dp[i][j] = dp[i][j-1]
????????字符串用charAt 比较好写
class Solution {
public int numDistinct(String s, String t) {
// 子序列出现的个数
// 卡哥的做法
// 使用二维数组 dp
// 记录s中t出现的个数
// 用s中的元素有多少种能组成t
// 0~i-1范围内的s中，出现多少次0~j-1范围内的t
// dp[i][j] 0~i 在0~j中出现的次数？
// 确定递推公式
// 若s[i-1]=t[j-1] dp[i][j] = dp[i-1][j-1]+dp[i-1][j]
// 其中 dp[i-1][j-1] 代表选中s[i-2]，能组成t[i-2]的个数,如今需要加上s[i-1]了一起带上
// 而dp[i-1][j] 代表去掉s[i-1]也可能组成t[j-1]，要把这些次数都加上
// 之前题目的dp[i-1][j-1]+1 代表最长的相同子序列的长度，出现相同的则+1
// dp[i][j]
// dp数组初始化
// 错误初始化
// s空串 t有值 dp[0][j] = 1 一种方法组成空串
// t空串 s有值 dp[i][0] = 0 没有方法组成s
// s空串 t空串 dp[0][0] = 1 空串有一种方法组成空串
// 正确初始化
// s空串 t有值 dp[0][j] = 0 s没有办法组成t
// t空串 s有值 dp[i][0] = 1 s有一种办法组成t(空串)
// s空串 t空串 dp[0][0] = 1 空串有一种方法组成空串
//确定遍历顺序
//从上到下，从左至右
// 举例推导dp数组
int[][] dp = new int[s.length()+1][t.length()+1];
//s中有多少元素能组成t ，若t为0 代表空串，一种元素能组成
for(int i=0;i<s.length();i++){
dp[i][0] = 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] + dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[s.length()][t.length()];
}
}