給定一個字串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= 'dogg', t = 'dog'為例
如果現在字尾相等 g = g ,那接下來有兩個選擇:
承接剛才的討論,假如剛剛選擇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[i, j] 代表 s[0~i] 能匹配 t[0~j] 的子序列總數目。
那最終所求是什麼?
目標是s能匹配t的子序列總數目 = DP[ len(s)-1, len(t)-1 ]
承接觀察點的討論
歸納匹配模式如下:
當字尾相等時,接下來有兩個選擇
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]
什麼是最小規模的問題?
如果過程中,目標t只剩下空字串時,代表找到一組子序列匹配目標t。
DP[i, j] = 1, if j = -1
如果過程中,發現s(匹配的材料)剩下空字串(材料用完了),而且t不是空字串,
代表無解。
DP[i, j] = 0 無解, if i = -1
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
s的index和t的index做匹配,最多有O(m*n)個匹配格子點。
最多有O(m*n)個匹配格子點,每個格子點需要紀錄對應的匹配子序列數量。
歸納匹配模式如下:
當字尾相等時,接下來有兩個選擇
1.讓目前字尾匹配t,s,t各自往前移動試著比較前綴字串。
2.捨棄這個機會,t保持不動,s往前移動試著匹配t。
當字尾相異時,只有一個選擇
沒有機會匹配,t保持不動,s往前移動試著匹配t。
如此反覆匹配流程,直到t剩下空字串時,代表找到一組子序列匹配目標t。
如果過程中發現s(匹配的材料)剩下空字串,而且t不是空字串,代表無解。
[1] Distinct Subsequences - LeetCode