用DP框架來思考 匹配目標字串的子序列 Distinct Subsequences_Leetcode #115

Jack van der Spoel on Unsplash

題目敘述 Distinct Subsequences

給定一個字串s和目標t，請問有多少個s的子序列可以完美匹配目標t ?

也就是說，有多少個s的子序列和目標t相等?

測試範例

Example 1:

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.

總共有三個，分別是:​

rabbbit
^^^^ ^^​

rabbbit
^^^ ^^^
​
rabbbit
^^ ^^^^

Example 2:

Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from s.

總共有五個，分別是:

babgbag
^^ ^

babgbag
^^    ^

babgbag
^    ^^

babgbag
  ^  ^^
  
babgbag
    ^^^

約束條件

Constraints:

• 1 <= s.length, t.length <= 1000

字串s, t 的長度都介於1~1000之間。

• s and t consist of English letters.

字串s, t都只會有英文字母。

觀察 怎麼讓s去匹配目標t

以s= 'dogg', t = 'dog'為例

如果現在字尾相等 g = g ，那接下來有兩個選擇:

1. 讓目前字尾匹配t，s,t各自往前移動試著比較'dog' 和 'do'
2. 捨棄這個機會，t保持不動，s往前移動試著匹配t，比較'dog' 和 'dog'

承接剛才的討論，假如剛剛選擇1.，那麼接著比較'dog'和'do'

這時侯字尾相異 'g' =/= 'o'，接下來只有一個選擇:

沒有機會匹配，s往前移動試著匹配t，比較'do' 和 'do'

總結歸納匹配模式如下:

當字尾相等時，接下來有兩個選擇

1.讓目前字尾匹配t，s,t各自往前移動試著比較前綴字串。

2.捨棄這個機會，t保持不動，s往前移動試著匹配t。

當字尾相異時，只有一個選擇

沒有機會匹配，t保持不動，s往前移動試著匹配t。

如此反覆匹配流程，直到t剩下空字串時，代表找到一組子序列匹配目標t。

如果過程中發現s(匹配的材料)剩下空字串，而且t不是空字串，代表無解。

演算法 DP動態規劃 + 字元匹配

1.定義DP狀態

DP[i, j] 代表 s[0~i] 能匹配 t[0~j] 的子序列總數目。

那最終所求是什麼?

目標是s能匹配t的子序列總數目 = ​DP[ len(s)-1, len(t)-1 ]

2.推導DP狀態轉移關係式

承接觀察點的討論

歸納匹配模式如下:

當字尾相等時，接下來有兩個選擇

1.讓目前字尾匹配t，s,t各自往前移動試著比較前綴字串。

2.捨棄這個機會，t保持不動，s往前移動試著匹配t。

DP[i, j]

= 選擇1的方法數 + 選擇2的方法數

= DP[i-1, j-1] + DP[i-1, j], if s[i] == t[j]

當字尾相異時，只有一個選擇

沒有機會匹配，t保持不動，s往前移動試著匹配t。

DP[i, j]

= 唯一一種選擇的方法數

= DP[i-1, j], if s[i] != t[j]

3.釐清DP初始條件

什麼是最小規模的問題?

如果過程中，目標t只剩下空字串時，代表找到一組子序列匹配目標t。

DP[i, j] = 1, if j = -1

如果過程中，發現s(匹配的材料)剩下空字串(材料用完了)，而且t不是空字串，
代表無解。

DP[i, j] = 0 無解, if i = -1

程式碼 DP動態規劃 + 字元匹配

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        
        # DP Table
        dp = {}

        def match(i, j):
            
            if (i, j) in dp:
                # Look-up DP Table
                return dp[i, j]

            if j == -1:
                # If target is empty stinrg, then s is subsequence by removing all characters
                dp[i, j] = 1
                return 1
            
            elif i == -1:
                # If source empty string, then it is impossible to have matching subsequence
                dp[i, j] = 0
                return 0
            
            elif s[i] == t[j]:
                
                # current character is match, backtrack to
                # matching on s[ 0...(i-1) ], t[ 0...(j-1) ], or
                # matching on s[ 0...(i-1) ], t[ 0...(j)   ]
                dp[i, j] = match(i-1, j-1) + match(i-1, j)
                return dp[i, j]
            
            else:
                
                # current character is mismatch, backtrack to
                # matching on s[ 0...(i-1) ], t[ 0...(j)   ]
                dp[i, j] = match(i-1, j)
                return dp[i, j]
            
        # ==================================================
        return match(len(s)-1, len(t)-1 )

複雜度分析

令字串s的長度為m
令字串t的長度為n

時間複雜度:O(mn)

s的index和t的index做匹配，最多有O(m*n)個匹配格子點。

空間複雜度:O(mn)

最多有O(m*n)個匹配格子點，每個格子點需要紀錄對應的匹配子序列數量。

關鍵知識點 怎麼讓s去匹配目標t

歸納匹配模式如下:

當字尾相等時，接下來有兩個選擇

1.讓目前字尾匹配t，s,t各自往前移動試著比較前綴字串。

2.捨棄這個機會，t保持不動，s往前移動試著匹配t。

當字尾相異時，只有一個選擇

沒有機會匹配，t保持不動，s往前移動試著匹配t。

如此反覆匹配流程，直到t剩下空字串時，代表找到一組子序列匹配目標t。

如果過程中發現s(匹配的材料)剩下空字串，而且t不是空字串，代表無解。

Reference

[1] Distinct Subsequences - LeetCode

回到DP特訓班目錄 和 學習路徑