目錄
🟥相異子序列數
本題取自 Leetcode 115. Distinct Subsequences
題目
Given two strings s and t, return the number of distinct subsequences of s which equals t.
The test cases are generated so that the answer fits on a 32-bit signed integer.
Example 1:
Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
-------
rabb it
rab bit
ra bbit
Example 2:
Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from s.
babgbag
-------
ba g
ba g
b ag
b ag
bag
Constraints:
1 <= s.length, t.length <= 1000
s and t consist of English letters.
分析
題目要求從s找出和t相同的子序列(subsequence),並計算不同的子序列總數量。
子序列指的是從s中刪除任意數量字母,剩下字母順序不變的字串。
本題用暴力法窮舉s
的所有子序列是不現實的,因為每個字母可取可不取,此舉將產生O(2^n)的複雜度。
雖然本題較複雜,經過前幾題的磨練,對於這類的字串題我們已經有個概念,關鍵還是在於如何取出字母進行「比對」。從這裡當出發點,來尋找分治法的突破口。
分治法
我們以t='bag'
, s='babgbag'
為例來拆解問題。
母問題求s
中有幾個子序列為t
,那麼子問題就是問:
給定
i
,j
,則s[:i+1]
裡面有幾個t[:j+1]
?
當j==0
時:s
當中有幾個'b'
?
很顯然總共是3個。不過,我們把s裡面「從頭開始到index=i為止」(即s[:i+1]
)一共有幾個'b'
,分別記錄在dp[0][i]
中。
例如,dp[0][3] == 2
,因為在'babg'
裡面一共有2個'b'
當j==1
時,s
當中有幾個'ba'
?
此時,我們先比對新增加的'a'
,發現在s
當中有2個'a'
分別位於i==1,5
的位置。
對於i==1
的'a'
,在其「前面」有1
個b
。
對於i==5
的'a'
,在其「前面」有3
個b
。
並且在dp[1][i]
紀錄「到i為止,前面」一共有幾個'ba'
因此,dp[1][5]
就會記錄為4
。
當j==2時,s
當中有幾個'bag'
?
一樣,先比對新增加的'g'
,發現在s
當中有2個'g'
分別位於i==3,6
的位置。
對於i==3
的'g'
,在其「前面」有1
個ba
。
對於i==6
的'g'
,在其「前面」有4
個ba
。
因此,dp[2][6]
會紀錄為5
至此,我們就找到了逐步的遞迴關係。
設計狀態、找出轉移式與最小問題
狀態:以count(i, j)表示s[:i+1]中有幾個子序列為t[j:+1]。
轉移式:先比對是否s[i] == t[j]
。
若s[i] != t[j]
:此時新增加的s[i]
沒有形成新的等於t[:j+1]的子序列。因此:
count(i, j) = count(i-1, j)
若s[i] == t[j]
:此時新增加的s[i]
所產生的子序列中,可能有等於t[:j+1]
的子序列。這取決於「在i
之前一共有多少子序列等於t[:j]
」,換言之,count(i-1,j-1)
。因此:
count(i, j) = count(i-1, j) + count(i-1, j-1)
邊界條件(最小問題):
-
當
i < 0
時,count(i, j) = 0
-
當
j == -1
時,count(i, j) = 1
唯一會用到j==-1
是計算count(i,0)
且s[i]==t[0]
,也就是只比對t
第一個字母時。讓count(i, -1) = 1
,就可以讓count(i,0)
算出正確的值。
母問題(題目所求):count(len(s)-1, len(t)-1)
實作
Top-Down DP
class Solution:
def numDistinct(self, s: str, t: str) -> int:
@cache
def count(i,j):
if j==-1: return 1
if i==-1: return 0
return count(i-1,j) + (count(i-1,j-1) if s[i]==t[j] else 0)
return count(len(s)-1, len(t)-1)
Bottom-Up DP
可以使用Rolling來降低一個空間維度。
class Solution:
def numDistinct(self, s: str, t: str) -> int:
dp = [1 if c==t[0] else 0 for c in s]
for target in t:
dp2 = [0]
for i, char in enumerate(s):
if char == target:
dp2.append(dp[i]+dp2[-1])
else:
dp2.append(dp2[-1])
dp = dp2
return dp[-1]
複雜度分析
時間複雜度
時間複雜度 = 狀態轉移數 x 計算複雜度
本題的狀態數 = O(n x m)
,n、m分別為s、t的長度
計算複雜度為O(1)
因此總時間複雜度 = O(n x m)
空間複雜度
空間複雜度 = 狀態數 = O(n x m)
若採用Rolling Bottom Up DP的技巧,則降低一個維度,空間複雜度 = O(m)
結語
在連續看了幾日字串類型的題目之後,是否Hard題也不再那麼艱澀了呢?
在前面文章提到過,當掌握了各個題型的基本題,觸類旁通就能夠解開類似題型但自己沒看過的題目。
本系列文到此剛好寫完了一半的篇幅,希望各位讀者至此已經掌握「分治法找子問題→設計狀態描述子問題→推導轉移式→實作出top-down或者bottom-up型態的DP程式碼」的這個基本流程,以及在實作時常用的一些技巧,如bottom-up加一格來處理邊界條件、rolling節省空間…等等。
如果有想要更深入說明的內容,也歡迎留言告訴我,會在後面的文章內補充!
以上為Day15的內容!感謝你的閱讀,如果有不同的想法或心得,歡迎留言一同討論!
本文也同步登載在我的個人部落格,記錄我的學習筆記與生活點滴,歡迎來逛逛。
經過與字串打交道的一周,明天起我們會轉移目標,開始下一種經典題型:遞增、遞減數列。在這個題型中我們大多會搭配使用Monotonic queue(漸進佇列)這個特殊的資料型態,其中有非常巧妙的構思,來達到降低時間複雜度的效果,敬請期待!