目錄

🟥相異子序列數

本題取自 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]中。

alt text

例如,dp[0][3] == 2 ,因為在'babg'裡面一共有2個'b'


j==1時,s當中有幾個'ba'

此時,我們先比對新增加的'a',發現在s當中有2個'a'分別位於i==1,5的位置。

alt text

對於i==1'a',在其「前面」有1b

alt text

對於i==5'a',在其「前面」有3b

alt text

並且在dp[1][i]紀錄「到i為止,前面」一共有幾個'ba'

因此,dp[1][5]就會記錄為4


當j==2時,s當中有幾個'bag'

一樣,先比對新增加的'g',發現在s當中有2個'g'分別位於i==3,6的位置。

alt text

對於i==3'g',在其「前面」有1ba

對於i==6'g',在其「前面」有4ba

因此,dp[2][6]會紀錄為5

alt text

至此,我們就找到了逐步的遞迴關係。

設計狀態、找出轉移式與最小問題

狀態:以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(漸進佇列)這個特殊的資料型態,其中有非常巧妙的構思,來達到降低時間複雜度的效果,敬請期待!