成都做营销型网站建设,js调用wordpress文章列表,58同城做网站要钱吗,重庆建设工程安全管理平台JAVA代码编写
392.判断子序列
给定字符串 s 和 t #xff0c;判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些#xff08;也可以不删除#xff09;字符而不改变剩余字符相对位置形成的新字符串。#xff08;例如#xff0c;ace是判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。
进阶
如果有大量输入的 S称作 S1, S2, … , Sk 其中 k 10亿你需要依次检查它们是否为 T 的子序列。在这种情况下你会怎样改变代码
致谢
特别感谢 pbrother 添加此问题并且创建所有测试用例。
示例 1
输入s abc, t ahbgdc
输出true示例 2
输入s axc, t ahbgdc
输出false提示
0 s.length 1000 t.length 10^4两个字符串都只由小写字符组成。
教程https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html
方法一动态规划
思路
五部曲
1.dp[i] [j] 表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度为dp[i] [j]。
2.确定递归公式
在确定递推公式的时候首先要考虑如下两种操作整理如下
if (s[i - 1] t[j - 1]) t中找到了一个字符在s中也出现了 if (s[i - 1] ! t[j - 1]) 相当于t要删除元素继续匹配
if (s[i - 1] t[j - 1])那么dp[i] [j] dp[i - 1] [j - 1] 1;因为找到了一个相同的字符相同子序列长度自然要在dp[i-1] [j-1]的基础上加1如果不理解在回看一下dp[i] [j]的定义
if (s[i - 1] ! t[j - 1])此时相当于t要删除元素t如果把当前元素t[j - 1]删除那么dp[i] [j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了即dp[i][j] dp[i][j - 1];
3.数组初始化
初始化均为0
4.遍历顺序
同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1] [j - 1] 和 dp[i] [j - 1]那么遍历顺序也应该是从上到下从左到右
5.举个例子
以示例一为例输入s “abc”, t “ahbgdc”dp状态转移图如下 复杂度分析
时间复杂度O(mn)其中m和n分别表示字符串s和字符串t的长度。空间复杂度O(mn)
class Solution {public boolean isSubsequence(String s, String t) {int m s.length(); int n t.length();int[][] dp new int[m1][n1];for(int i 1; i m; i){for(int j 1; j n; 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];}}}return dp[m][n] m ? true: false;}
}方法二双指针法
思路初始化两个指针i和j分别指向s和t的起始位置。
然后进入循环循环条件是i小于s的长度且j小于t的长度。在每次循环中比较s.charAt(i)和t.charAt(j)两个字符是否相等如果相等则说明s中的当前字符匹配到了t中的当前字符此时将i向后移动一位表示已经匹配成功一个字符。
无论是否匹配成功都将j向后移动一位继续比较下一个字符。
最后循环结束后判断i是否等于s的长度如果相等则说明s中的所有字符都成功匹配到了t的子序列中返回true否则返回false。
复杂度分析
时间复杂度O(min(s.length(), t.length()))其中s.length()和t.length()分别表示字符串s和字符串t的长度。空间复杂度O(1)
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();}public static void main(String[] args) {Solution solution new Solution();System.out.println(solution.isSubsequence(abc,ahbgdc));}
}115.不同的子序列
给你两个字符串 s 和 t 统计并返回在 s 的 子序列 中 t 出现的个数结果需要对 109 7 取模。
示例 1
输入s rabbbit, t rabbit
输出3
解释
如下所示, 有 3 种可以从 s 中得到 rabbit 的方案。
rabbbit
rabbbit
rabbbit示例 2
输入s babgbag, t bag
输出5
解释
如下所示, 有 5 种可以从 s 中得到 bag 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag提示
1 s.length, t.length 1000s 和 t 由英文字母组成
教程https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html
方法一动态规划
思路
五部曲
1.定义数组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]。
所以当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];
3.数组初始化 for (int i 0; i s.length() 1; i) {dp[i][0] 1;}4.遍历顺序
从递推公式dp[i][j] dp[i - 1] [j - 1] dp[i - 1] [j]; 和 dp[i] [j] dp[i - 1] [j]; 中可以看出dp[i] [j]都是根据左上方和正上方推出来的。
5.举个例子
以s“baegg”tbag为例推导dp数组状态如下 复杂度分析
时间复杂度O(mn)空间复杂度O(mn)
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()];}
}
