温州专业网站建设推广,临淄区住房和城乡建设局网站,传奇手游新开网站,做婚姻网站赚钱算法训练营 day58 动态规划 判断子序列 不同的子序列
判断子序列
392. 判断子序列 - 力扣#xff08;LeetCode#xff09;
给定字符串 s 和 t #xff0c;判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些#xff08;也可以不删除#xff09;字符而…算法训练营 day58 动态规划 判断子序列 不同的子序列
判断子序列
392. 判断子序列 - 力扣LeetCode
给定字符串 s 和 t 判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。
进阶
如果有大量输入的 S称作 S1, S2, … , Sk 其中 k 10亿你需要依次检查它们是否为 T 的子序列。在这种情况下你会怎样改变代码 确定dp数组dp table以及下标的含义 dp[i][j] 表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度为dp[i][j]。 注意这里是判断s是否为t的子序列。即t的长度是大于等于s的。 确定递推公式 在确定递推公式的时候首先要考虑如下两种操作整理如下 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]; dp数组如何初始化 从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]所以dp[0][0]和dp[i][0]是一定要初始化的。 这里大家已经可以发现在定义dp[i][j]含义的时候为什么要表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度为dp[i][j]。 因为这样的定义在dp二维矩阵中可以留出初始化的区间如图 如果要是定义的dp[i][j]是以下标i为结尾的字符串s和以下标j为结尾的字符串t初始化就比较麻烦了。
dp[i][0] 表示以下标i-1为结尾的字符串与空字符串的相同子序列长度所以为0. dp[0][j]同理。
确定遍历顺序
同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]那么遍历顺序也应该是从上到下从左到右
如图所示 举例推导dp数组
以示例一为例输入s “abc”, t “ahbgdc”dp状态转移图如下 dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度所以如果dp[s.size()][t.size()] 与 字符串s的长度相同说明s与t的最长相同子序列就是s那么s 就是 t 的子序列。
图中dp[s.size()][t.size()] 3 而s.size() 也为3。所以s是t 的子序列返回true。
class Solution {public boolean isSubsequence(String s, String t) {int[][] dp new int[s.length()1][t.length()1];char[] number1 s.toCharArray();char[] number2 t.toCharArray();for (int i 1; i number1.length; i) {for (int j 1; j number2.length; j) {if (number1[i-1]number2[j-1]) dp[i][j] dp[i-1][j-1]1;else dp[i][j] dp[i][j-1];System.out.print(dp[i][j]);}System.out.println();}return dp[number1.length][number2.length]s.length();}
}不同的子序列
115. 不同的子序列 - 力扣LeetCode
给定一个字符串 s 和一个字符串 t 计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指通过删除一些也可以不删除字符且不干扰剩余字符相对位置所组成的新字符串。例如“ACE” 是 “ABCDE” 的一个子序列而 “AEC” 不是
题目数据保证答案符合 32 位带符号整数范围。
确定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子串和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]; 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[i][j] dp[i - 1][j - 1] dp[i - 1][j]; 和 dp[i][j] dp[i - 1][j]; 中可以看出dp[i][j]都是根据左上方和正上方推出来的。 所以遍历的时候一定是从上到下从左到右这样保证dp[i][j]可以根据之前计算出来的数值进行计算。
举例推导dp数组
以s“baegg”tbag为例推导dp数组状态如下 如果写出来的代码怎么改都通过不了不妨把dp数组打印出来看一看是不是这样的。
class Solution {public int numDistinct(String s, String t) {char[] number1 s.toCharArray();char[] number2 t.toCharArray();int[][] dp new int[number1.length1][number2.length1];for (int i 0; i number1.length; i) {dp[i][0]1;}for (int i 1; i number1.length ; i) {for (int j 1; j number2.length ; j) {if (number1[i-1]number2[j-1]) dp[i][j]dp[i-1][j-1]dp[i-1][j];else dp[i][j] dp[i-1][j];}}return dp[number1.length][number2.length];}
}
