题目
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
例：
输入：s = "abc", t = "ahbgdc"
输出：true
方法：动态规划
思路同 1143. 最长公共子序列，区别在于一个求长度，一个求长度是否等于字符串 s
-
dp[i][j] 表示以下标 i-1 为结尾的字符串 s 和以下标 j-1 为结尾的字符串 t 的相同子序列的长度
※ dp[i][j] 对应 s[i-1] 和 t[j-1] 的原因是为初始化留出位置
-
外层循环表示对字符串 s 的循环，内层循环表示对字符串 t 的循环
- 若字符串 s 的下标为 i-1 处的字符等于字符串 t 的下标为 j-1 处的字符，即 s[i-1] == t[j-1]，那么相同子序列的长度加一
- 否则，此时的相同子序列的长度即为以下标 i-1 为结尾的字符串 s 和以下标 j-2 为结尾的字符串 t 的相同子序列的长度 dp[i][j-1]
判断得到的相同子序列的长度是否等于字符串 s 的长度，若相等则表示字符串 s 为字符串 t 的子序列
class Solution(object):
def isSubsequence(self, s, t):
dp = [[0] * (len(t)+1) for row 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] + 1
else:
dp[i][j] = dp[i][j-1]
if dp[-1][-1] == len(s):
return True
return False
参考
代码相关：https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html
