继续子序列的练习！

第一题

392. Is Subsequence

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

首先想到双指针的解法，复杂度为O(n)，也能接受。不过既然在练习动态规划，就还是按照动态规划的思路去解。

在确定递推公式的时候，首先要考虑如下两种操作，整理如下：

• 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

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];

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]if dp[-1][-1] == len(s):return Truereturn False

第二题

115. Distinct Subsequences

Given two strings s and t, return the number of distinct subsequences of s which equals t.

The test cases are generated so that the answer fits on a 32-bit signed integer.

这道题双指针就没法做了，只能用动态规划。

递推公式为：dp[i][j] = dp[i - 1][j];

从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j] 是从上方和左上方推导而来，那么 dp[i][0] 和dp[0][j]是一定要初始化的。

class Solution:def numDistinct(self, s: str, t: str) -> int:n1, n2 = len(s), len(t)if n1 < n2:return 0dp = [0 for _ in range(n2 + 1)]dp[0] = 1for i in range(1, n1 + 1):prev = dp.copy()end = i if i < n2 else n2for j in range(1, end + 1):if s[i - 1] == t[j - 1]:dp[j] = prev[j - 1] + prev[j]else:dp[j] = prev[j]return dp[-1]