如何做网站教学,怎么制作网页表白,瑜伽网站设计,代写文章哪里找写手本文目录 392.判断子序列做题看文章 115.不同的子序列做题看文章 以往忽略的知识点小结个人体会 392.判断子序列
代码随想录#xff1a;392.判断子序列 Leetcode#xff1a;392.判断子序列
做题
借鉴Day53中1143.最长公共子序列的思路#xff0c;最后改一下判断逻辑即可。… 本文目录 392.判断子序列做题看文章 115.不同的子序列做题看文章 以往忽略的知识点小结个人体会 392.判断子序列
代码随想录392.判断子序列 Leetcode392.判断子序列
做题
借鉴Day53中1143.最长公共子序列的思路最后改一下判断逻辑即可。
class Solution:def isSubsequence(self, s: str, t: str) - bool:dp [[0] * (len(s)1) for _ in range(len(t)1)]for i in range(1, len(t)1):for j in range(1, len(s)1):if t[i-1] s[j-1]:dp[i][j] dp[i-1][j-1] 1else:dp[i][j] max(dp[i][j-1], dp[i-1][j])if dp[len(t)][len(s)] len(s):return Trueelse:return False时间复杂度O(n × m) 空间复杂度O(n × m)
看文章
思路一致。
115.不同的子序列
代码随想录115.不同的子序列 Leetcode115.不同的子序列
做题
无思路。
看文章
这道题很难题解也看了很久。 动规五部曲 确定dp数组dp table以及下标的含义。 dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。 确定递推公式。这一类问题基本是要分析两种情况 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]只有一部分组成不用s[i - 1]来匹配就是模拟在s中删除这个元素即dp[i - 1][j]。 dp数组如何初始化。 dp[i][0]以i-1为结尾的s可以随便删除元素出现空字符串的个数。那么dp[i][0]一定都是1因为也就是把以i-1为结尾的s删除所有元素出现空字符串的个数就是1。 dp[0][j]空字符串s可以随便删除元素出现以j-1为结尾的字符串t的个数。那么dp[0][j]一定都是0s如论如何也变成不了t。 确定遍历顺序。 外部遍历 s内部遍历 t。 举例推导dp数组。
代码如下
class Solution:def numDistinct(self, s: str, t: str) - int:dp [[0] * (len(t)1) for _ in range(len(s)1)]for i in range(len(s)1):dp[i][0] 1for i in range(1, len(s)1):for j in range(1, len(t)1):if s[i-1] t[j-1]:dp[i][j] dp[i-1][j-1] dp[i-1][j]else:dp[i][j] dp[i-1][j]return dp[len(s)][len(t)]以往忽略的知识点小结
回到动规五部曲的基本思路特别是dp数组的含义
个人体会
完成时间1h30min。 心得115.不同的子序列比较难看了好久需要回归到动规五部曲的基本思路特别是dp数组的含义。
