保定网站建设保定,金寨县住房和城乡建设部网站,东莞市建设局门户网站,专业团队p图392.判断子序列
力扣题目链接(opens new window)
给定字符串 s 和 t #xff0c;判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些#xff08;也可以不删除#xff09;字符而不改变剩余字符相对位置形成的新字符串。#xff08;例如#xff0c;判断 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
两个字符串都只由小写字符组成。
#算法公开课
《代码随想录》算法视频公开课 (opens new window)动态规划用相似思路解决复杂问题 | LeetCode392.判断子序列 (opens new window)相信结合视频再看本篇题解更有助于大家对本题的理解。
#思路
这道题也可以用双指针的思路来实现时间复杂度也是O(n)
这道题应该算是编辑距离的入门题目因为从题意中我们也可以发现只需要计算删除的情况不用考虑增加和替换的情况。
所以掌握本题的动态规划解法是对后面要讲解的编辑距离的题目打下基础。
动态规划五部曲分析如下
确定dp数组dp table以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度为dp[i][j]。
注意这里是判断s是否为t的子序列。即t的长度是大于等于s的。
有同学问了为啥要表示下标i-1为结尾的字符串呢为啥不表示下标i为结尾的字符串呢
为什么这么定义我在 718. 最长重复子数组 (opens new window)中做了详细的讲解。
其实用i来表示也可以
但我统一以下标i-1为结尾的字符串来计算这样在下面的递归公式中会容易理解一些如果还有疑惑可以继续往下看。
确定递推公式
在确定递推公式的时候首先要考虑如下两种操作整理如下
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];
其实这里 大家可以发现和 1143.最长公共子序列 (opens new window)的递推公式基本那就是一样的区别就是 本题 如果删元素一定是字符串t而 1143.最长公共子序列 是两个字符串都可以删元素。
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]同理。
vectorvectorint dp(s.size() 1, vectorint(t.size() 1, 0));1
确定遍历顺序
同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]那么遍历顺序也应该是从上到下从左到右
如图所示 举例推导dp数组
以示例一为例输入s abc, t ahbgdcdp状态转移图如下 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。
动规五部曲分析完毕C代码如下
class Solution {
public:bool isSubsequence(string s, string t) {vectorvectorint dp(s.size() 1, vectorint(t.size() 1, 0));for (int i 1; i s.size(); i) {for (int j 1; j t.size(); j) {if (s[i - 1] t[j - 1]) dp[i][j] dp[i - 1][j - 1] 1;else dp[i][j] dp[i][j - 1];}}if (dp[s.size()][t.size()] s.size()) return true;return false;}
};1 2 3 4 5 6 7 8 9 10 11 12 13 14
时间复杂度O(n × m)空间复杂度O(n × m)
#总结
这道题目算是编辑距离的入门题目毕竟这里只是涉及到减法也是动态规划解决的经典题型。
这一类题都是题目读上去感觉很复杂模拟一下也发现很复杂用动规分析完了也感觉很复杂但是最终代码却很简短。
在之前的题目讲解中我们讲了 1143.最长公共子序列 (opens new window)大家会发现 本题和 1143.最长公共子序列 的相似之处。
编辑距离的题目最能体现出动规精髓和巧妙之处大家可以好好体会一下。
#其他语言版本
#Java:
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;}}
}
