392. 判斷子序列
這個微軟面試的時候考過? 雙指針就行
編輯距離入門題：
思路是一樣的 相同字符+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 False115. 不同的子序列?
s和t是不對稱的 尾端相同的情況相當于加一波可能性 第一行和第一列也不對稱
這個要注意
class Solution:def numDistinct(self, s: str, t: str) -> int:dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]for i in range(len(s)):dp[i][0]=1for j in range(1,len(t)):dp[0][j]=0for 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]+dp[i-1][j]else:dp[i][j]=dp[i-1][j]return dp[-1][-1]
)
