家教网站建设的推广,兰州光辉网站建设,长沙制作网页的基本步骤,做网站优化的公司提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录
一、392.判断子序列
思路
二、115.不同的子序列
思路 一、392.判断子序列
给定字符串 s 和 t #xff0c;判断 s 是否为 t 的子序列。
字符串的一个子序列是… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录
一、392.判断子序列
思路
二、115.不同的子序列
思路 一、392.判断子序列
给定字符串 s 和 t 判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。
示例 1
输入s abc, t ahbgdc输出true
示例 2
输入s axc, t ahbgdc输出false
提示
0 s.length 1000 t.length 10^4
两个字符串都只由小写字符组成。
思路
这道题其实和昨天那道最长公共子序列类似只不过在最后加入一个判断如果最长公共子序列的长度等于s的长度那么就返回true否则返回false。
class Solution {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;}}
}
二、115.不同的子序列
给定一个字符串 s 和一个字符串 t 计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指通过删除一些也可以不删除字符且不干扰剩余字符相对位置所组成的新字符串。例如ACE 是 ABCDE 的一个子序列而 AEC 不是
题目数据保证答案符合 32 位带符号整数范围。 提示
0 s.length, t.length 1000s 和 t 由英文字母组成
思路
这道题比上一题稍微难一些。
dp数组dp table以及下标的含义dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
这一类问题基本是要分析两种情况
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[i - 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];
dp数组初始化
从递推公式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][j]的定义不要凭感觉初始化。
dp[i][0]表示什么呢
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。
最后就要看一个特殊位置了即dp[0][0] 应该是多少。
dp[0][0]应该是1空字符串s可以删除0个元素变成空字符串t。
举例推导dp数组
以sbaeggtbag为例推导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()];}
}1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
