代码随想录算法训练营第五十四天｜392.判断子序列， 115.不同的子序列

本文主要是介绍代码随想录算法训练营第五十四天｜392.判断子序列， 115.不同的子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

392.判断子序列

https://leetcode.com/problems/is-subsequence/description/

思路：第一种方法使用动态规划， 也就是寻找最长公共字符串， 如果最长公共字符串等于s的长度， 输出 True， 反之输出False。 

第二张方法使用双指针， 在外层循环字符串s， 然后内层开始找到s[0] 的位置。如果能找到， 例如位置是 j0, 然后开始从 t[j0:] 找 s[1], 位置是 j1, .... 如果没有找到的字符， 返回 False, 否则返回 True。 

难点： 无

# 动态规划，LCS
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)

# 指针
class Solution:def isSubsequence(self, s: str, t: str) -> bool:isSubs = Truefor char in s:try:index=t.index(char)except:isSubs=Falsebreakt=t[index+1:]return isSubs

115.不同的子序列

https://leetcode.com/problems/distinct-subsequences/description/

思路： 这个问题有点难度， 判断字符串s 中有多少种 t 的组合， 我们首先定义dp 数组， dp 数组的值含义是 s[0:j] 中 一共含有多少种 t[0:i]. 例如 s = aabb , t = ab, 那么 dp[1][1] = 1 dp[1][2] = 2 dp[2][2] = 0, dp[2][3] = 2 这样。 

然后是递推关系， 如果s[j-1] != t[i-1], 那么我们 s[0:j] 中含有的 t[0:i] 就等于 s[0:j-1] 中含有的。 如果  s[j-1] == t[i-1]， 那么 s[0:j] 中含有的 t[0:i] 就等于 s[0:j-1] 中含有的 t[0:i-1] 加上  s[0:j-1] 中含有的 t[0:i]。 

难点： 要理清楚递推关系， 不要忘了相等的时候的状态是有两个位置相加得来的。 

class Solution:def numDistinct(self, s: str, t: str) -> int:'''dp: march methods for string t[0:i] in s[0:j].if s[i-1] == t[j-1], dp = dp[i-1][j-1] + dp[i][j-1] which means if last letter marches, we sum methods usig last marched letter and methods without using it. if s[i-1] != t[j-1] dp = dp[i][j-1].'''dp = [[0] * (len(s) + 1) for _ in range(len(t)+1)]dp[0] = [1] * (len(s) + 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] + dp[i][j-1]else:dp[i][j] = dp[i][j-1]return dp[-1][-1]

这篇关于代码随想录算法训练营第五十四天｜392.判断子序列， 115.不同的子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---