392.判断子序列
1、双指针
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
m, n = len(s), len(t)
i, j = 0, 0
while m > i and n > j:
if s[i] == t[j]:
i += 1
j += 1
return m == i
2、动态规划
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
m, n = len(s), len(t)
# dp 数组代表 s 以 i-1 结尾和 t 以 j 结尾的最长公共子序列
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+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[m][n] == m:
return True
else:
return False
class Solution:
def numDistinct(self, s: str, t: str) -> int:
n, m = len(s), len(t)
# dp 数组代表 s 以 i-1 结尾中包含 t 以 j-1 结尾的个数
dp = [[0] * (m+1) for _ in range(n+1)]
# 初始化
for i in range(n+1):
dp[i][0] = 1
for i in range(1, n+1):
for j in range(1, m+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[n][m]