判斷子序列
題目鏈接
給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。
字符串的一個(gè)子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對(duì)位置形成的新字符串。（例如，"ace"是"abcde"的一個(gè)子序列，而"aec"不是）。
示例 1：
輸入：s = "abc", t = "ahbgdc"
輸出：true
示例 2：
輸入：s = "axc", t = "ahbgdc"
輸出：false
提示：
0 <= s.length <= 1000 <= t.length <= 10^4- 兩個(gè)字符串都只由小寫字符組成。
首先，我們定義一個(gè)二維布爾數(shù)組 dp，其中 dp[i][j] 表示字符串 t 的前 i 個(gè)字符是否包含字符串 s 的前 j 個(gè)字符作為子序列。我們的目標(biāo)是求出 dp[t.length()][s.length()]。
動(dòng)態(tài)規(guī)劃的轉(zhuǎn)移方程如下：
-
當(dāng) s[j] != t[i] 時(shí)，dp[i][j] = dp[i-1][j]。這表示如果當(dāng)前考察的字符 t[i] 和 s[j] 不相等，那么 t 的前 i 個(gè)字符是否包含 s 的前 j 個(gè)字符作為子序列的結(jié)果與 t 的前 i-1 個(gè)字符是否包含 s 的前 j 個(gè)字符作為子序列的結(jié)果相同。
-
當(dāng) s[j] == t[i] 時(shí)，我們有兩種選擇：
- 我們可以選擇使用 t[i] 來匹配 s[j]，此時(shí)我們需要查看 t 的前 i-1 個(gè)字符是否包含 s 的前 j-1 個(gè)字符作為子序列，這就是 dp[i-1][j-1]。
- 我們也可以選擇不使用 t[i] 來匹配 s[j]，即我們跳過 t[i]，查看 t 的前 i-1 個(gè)字符是否包含 s 的前 j 個(gè)字符作為子序列，這就是 dp[i-1][j]。
因此，當(dāng) s[j] == t[i] 時(shí)，dp[i][j] = dp[i-1][j-1] || dp[i-1][j]。如果 t 的前 i-1 個(gè)字符包含 s 的前 j-1 個(gè)字符作為子序列，或者 t 的前 i-1 個(gè)字符包含 s 的前 j 個(gè)字符作為子序列，那么 t 的前 i 個(gè)字符就包含 s 的前 j 個(gè)字符作為子序列。文章來源：http://www.zghlxwxcb.cn/news/detail-604846.html
下面是使用 Python 實(shí)現(xiàn)的代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-604846.html
def isSubsequence(s, t):
m, n = len(t), len(s)
dp = [[False] * (n + 1) for _ in range(m + 1)]
# 當(dāng) s 為空字符串時(shí)，它是任何字符串的子序列
for i in range(m + 1):
dp[i][0] = True
for i in range(1, m + 1):
for j in range(1, min(i + 1, n + 1)): # j 不能大于 i
if t[i - 1] == s[j - 1]:
dp[i][j] = dp[i - 1][j - 1] or dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
return dp[m][n]
到了這里，關(guān)于每日一題之判斷子序列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
