给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,”ace”是”abcde”的一个子序列,而”aec”不是)。 进阶: 如果有大量输入的 S,称作 S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码? 示例 1: 输入:s = “abc”, t = “ahbgdc” 输出:true 示例 2: 输入:s = “axc”, t = “ahbgdc” 输出:false 提示:
本题其实不使用动态规划的思路也是能够解出来的 ,并且时间复杂度 和 空间复杂度更低。 因为题目中问的是 s 是否为t 的自序列, 我们自需要顺序遍历 t ,然后对比是否 s中也出现, 并且相对顺序不能变更即可。 代码实现中有。
如果使用·动态规划思路还是那个思路, 只是最后需要对比是否相同在自序列的长度 == s的长度即可。
还有就是在遍历的时候 如果
if(s.charAt(i-1) != t.charAt(j-1)){
//相当于t要删除元素,继续匹配
dp[i][j] = dp[i][j-1];
}
class Solution {
public boolean isSubsequence(String s, String t) {
//dp[i] 表示 容量为 i 的数组, 看是否能被填满
//i 为子序列 s 填充物为 t 要求保持相对顺序不变
// int []dp = new int[s.length() + 1];
if(s.length() == 0 && t.length() >=0 ) return true;
if(s.length() ==0 || t.length() == 0) return false;
if(s.length() > t.length()) return false;
int j =0 ;
for(int i= 0 ;i < t.length(); i++){
if(s.charAt(j) == t.charAt(i)){
j++;
if(j == s.length()) break;
}
}
if(j == s.length()){
return true;
}
return false;
}
}
class Solution {
public boolean isSubsequence(String s, String t) {
//dp[i][j] 表示 下标为 i-1的字符串s 和 下标为 j-1的字符串t 他们相同子序列的长度为 dp[i][j]
int [][]dp = new int[s.length() +1][t.length() + 1];
int res= 0;
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] + 1;
}else{
dp[i][j] = dp[i][j-1];
}
}
}
return dp[s.length()][t.length()] == s.length();
}
}
给你两个字符串 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 提示:
按照题目中的问题来定义dp数组的含义。
dp[i][j] 表示 长度为i-1 的 s的自序列 在长度为 j-1 的t中出现的次数
其实为啥这样定义我也是有点云里雾里的, 但是按照动态规划的思路, 自然而然你就会往这方面去向想。 然后再按照递归五部曲的顺序去思考每一步的实现可能性, 最后再写即可。
定义出来了, 但是本题还是有问题, 因为不太清楚如何确定递推公式。
如果s[i-1] == t[j-1]
那么dp数组该如何进行遍历。 如果不相等 那又该如何 ?
当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中 t 的个数。只需要考虑s删除某个字符的问题, 而不需要考虑t .如下图
同理不相等的时候 也是这样思考。
通过上图我们可以看出, dp[i][j] 是由上方 和 dp[i-1][j-1] 推导出来的, 所以需要对其进行初始化赋值
dp[i][0] 表示:以i-1为结尾的s可以随便删除元素,出现空字符串的个数。dp[0][0]应该是1,空字符串s,可以删除0个元素,变成空字符串t。
class Solution {
public int numDistinct(String s, String t) {
int [][]dp = new int[s.length() + 1][t.length()+1];
//dp[i][j] 表示 长度为i-1 的 s的自序列 在长度为 j-1 的t中出现的次数
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{
//我们这里考虑的是s中有多个t的问题, 所以只需要删除t中的进行比较
dp[i][j] = dp[i-1][j];
}
}
}
return dp[s.length()][t.length()];
}
}
给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 示例 1: 输入: word1 = “sea”, word2 = “eat” 输出: 2 解释: 第一步将 “sea” 变为 “ea” ,第二步将 “eat “变为 “ea” 示例 2: 输入:word1 = “leetcode”, word2 = “etco” 输出:4 提示:
按照题目中的要求 ,通过dp数组来对问题进行定义
dp[i][i] 表示 字符串长度为i-1的word1 和 字符串长度为 j-1 的word2, 如果想要两个字符串相等, 所需要的最小步数为dp[i][j]
如此就会出现两种情况。
如果**word1.charAt(i-1) == word2.charAt(j-1)**
dp数组如何推导
按照之前的递推思路, 那么就是通过dp[i-1][j-1]
从而得到dp[i][j]
, 因为题目中要求得到的是最小步数,所以这里需要进行 + 1操作
如果**word1.charAt(i-1) != word2.charAt(j-1)**
dp数组如何推导
不相等的时候就可以通过之前删除word中的字符时所用到的最小步数来推导 。如图
比较:dp[i][j-1]
和 dp[i-1][j]
二者通过删除字符 使之相同所需要的最少步数的最小值来获取, 然后最小值 + 1 就是需要的dp[i][j]
初始化
dp[i][0]
表示word2的长度为0 ,word1的长度为i ,如果想要两者相同, 所需要的最少步数是dp[i][0]
。
所以这里如果想要两者相同, 那么就需要将word1也删除到 长度为 0的情况才行。所以初始化为 dp[i][0] = i
, 同理,dp[0][j]
也是 ,如果想要两者相同, 那么就需要进行初始化为 j
class Solution {
public int minDistance(String word1, String word2) {
//dp[i][j] 表示 单词长度为 i -1 的word1 和单词长度为 j-1的word2 所需要的最少步数为dp[i][j]
int [][]dp = new int[word1.length() + 1][word2.length() + 1];
//初始化
for (int i = 0; i <= word1.length(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.length(); j++) dp[0][j] = j;
//确定递推公式
//如果w1[i] == w2[j]的时候
//如果w1[i] != w2[j]的时候
for(int i =1 ; i <= word1.length(); i++){
for(int j = 1; j <= word2.length();j++){
if(word1.charAt(i-1) == word2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1] +1);
}
}
}
return dp[word1.length()][word2.length()];
}
}