目錄

🟥相異子序列數

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