392. 判斷子序列
給定字符串?s?和?t?，判斷?s?是否為?t?的子序列。
字符串的一個(gè)子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對(duì)位置形成的新字符串。（例如，"ace"是"abcde"的一個(gè)子序列，而"aec"不是）。
思路：
1. 使用哈希統(tǒng)計(jì)兩個(gè)序列的二十六個(gè)字母的出現(xiàn)個(gè)數(shù)。
2. 動(dòng)態(tài)規(guī)劃 ，與最長(zhǎng)公共子序列類似，判斷最長(zhǎng)公共子序列長(zhǎng)度是否等于s，由于判斷s是否為t的s[j-1] ！= t[i-1] 時(shí)，狀態(tài)的轉(zhuǎn)移只能從 t 的前 i-1個(gè)字母和與s的前j個(gè)字母的最大公共子序列長(zhǎng)度轉(zhuǎn)移。
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
dp = [[0] * (len(s) + 1) for _ in range(len(t) + 1)]
for i in range(1, len(t) + 1):
for j in range(1, len(s) + 1):
if t[i-1] == s[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = dp[i-1][j]
return dp[-1][-1] == len(s)115. 不同的子序列
給你兩個(gè)字符串?s?和?t?，統(tǒng)計(jì)并返回在?s?的?子序列?中?t?出現(xiàn)的個(gè)數(shù)，結(jié)果需要對(duì)?109?+ 7 取模。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-729150.html
思路：動(dòng)態(tài)規(guī)劃，dp[i][j]定義為，s[:i] 的子序列中t[:j]出現(xiàn)的個(gè)數(shù)，轉(zhuǎn)移方程為，當(dāng)s[i-1] == t[j-1]時(shí)，dp[i][j] = dp[i-1][j-1](使用s[i-1]匹配t[j-1], 使用之前的元素匹配t[:j-1]) + dp[i-1][j]（使用之前的元素匹配t[:j])?,當(dāng)s[i-1] ！= t[j-1] 時(shí), dp[i][j] = dp[i-1][j]（使用之前的某個(gè)元素匹配t[j-1])。初始化dp[i][0] = 1，dp[0][j]=0(j>0)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-729150.html
class Solution:
def numDistinct(self, s: str, t: str) -> int:
dp = [[0]*(len(t)+1) for _ in range(len(s) + 1)]
for n in range(len(s) + 1):
dp[n][0] = 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]
else:
dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
return dp[-1][-1]到了這里，關(guān)于代碼隨想錄 動(dòng)態(tài)規(guī)劃 判斷子序列，不同的子序列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
