面试150 判断子序列

思路

在思路上可以联想到动态规划。我们首先定义一个二维数组 dp[i][j]，表示字符串s的前 i 个字符在字符串 t 的前 j个字符中，作为子序列所能匹配的最长长度。初始化dp数组后，遍历 s和 t的字符：若当前字符 s[i-1] == t[j-1]，说明两字符匹配，可以在之前的基础上加一，即 dp[i][j] = dp[i-1][j-1] + 1；否则，说明当前位置不匹配，需要从之前的状态中选择最大值回退，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。每次更新时，可记录 dp[i][j] 的最大值 result。最后判断 result 是否等于字符串 s的长度，若相等则说明 s 是 t的一个子序列，否则不是。

class Solution:def isSubsequence(self, s: str, t: str) -> bool:m=len(s)n=len(t)dp=[[0]*(n+1) for _ in range(m+1)]dp[0][0]=0result=0for 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]+1elif s[i-1]!=t[j-1]:dp[i][j]=max(dp[i-1][j],dp[i][j-1])if dp[i][j]>result:result=dp[i][j]if m==result:return Trueelse:return False