成都网站建设网站,网站开发获取本地ip,模板之家免费下载方法,黄陌陌网站怎么做目录 392.判断子序列思路代码 115.不同的子序列思路代码 392.判断子序列
Leetcode 思路
dp[i][j] 表示以下标i-1为结尾的字符串s#xff0c;和以下标j-1为结尾的字符串t#xff0c;相同子序列的长度为dp[i][j]递推公式#xff1a; 初始化#xff1a;为0遍历顺序#xff… 目录 392.判断子序列思路代码 115.不同的子序列思路代码 392.判断子序列
Leetcode 思路
dp[i][j] 表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度为dp[i][j]递推公式 初始化为0遍历顺序从上到下从左到右举例输入s “abc”, t “ahbgdc”dp状态转移图如下
代码
class Solution:def isSubsequence(self, s: str, t: str) - bool:dp [[0] * (len(t) 1) for _ in range(len(s) 1)]for 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] 1else:dp[i][j] dp[i][j - 1]return dp[-1][-1] len(s)时间复杂度O(n × m)空间复杂度O(n × m)
115.不同的子序列
Leetcode 思路
dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][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[i][0] 和dp[0][j]是一定要初始化的。dp[i][0] 1, dp[0][j] 0, dp[0][0] 1。 遍历顺序从上到下从左到右举例推导以s“baegg”tbag为例推导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] dp[i - 1][j - 1]else:dp[i][j] dp[i - 1][j]return dp[-1][-1]时间复杂度O(n × m)空间复杂度O(n × m)
