Given a string S and a string T, count the number of distinct subsequences of S which equals T.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE"
is a subsequence of "ABCDE"
while "AEC"
is not).
Example 1:
Input: S ="rabbbit"
, T ="rabbit"
Explanation: As shown below, there are 3 ways you can generate "rabbit" from S.
Output: 3
(The caret symbol ^ means the chosen letters)rabbbit
^^^^ ^^rabbbit
^^ ^^^^rabbbit
^^^ ^^^
Example 2:
Input: S ="babgbag"
, T ="bag"
Explanation: As shown below, there are 5 ways you can generate "bag" from S.
Output: 5
(The caret symbol ^ means the chosen letters)babgbag
^^ ^babgbag
^^ ^babgbag
^ ^^babgbag
^ ^^babgbag
^^^ 这个题目思路是用两个sequence的dynamic programming,mem[l1 + 1][l2 + 1] # mem[i][j]表示number of distinct subsequences of S[: i + 1] which equals T[: j + 1]
mem[i][j] = mem[i - 1][j] + mem[i - 1][j - 1] if s1[i - 1] == s2[j - 1] # 如果相等,可以选择配对或者不配对
mem[i - 1][j] if s1[i - 1] != s2[j - 1] # 如果不相等,就必须把最后一个舍弃掉 初始化: mem[i][0] = 1, mem[0][j] = 0 (j > 1) code
class Solution:
def disSubsequences(self, s1, s2):
l1, l2 = len(s1), len(s2)
mem = [[0] * (l2 + 1) for _ in range(l1 + 1)]
for i in range(l1 + 1):
mem[i][0] = 1
for i in range(1, l1 + 1):
for j in range(1, l2 + 1):
mem[i][j] = mem[i - 1][j] if s1[i - 1] != s2[j - 1] else mem[i - 1][j] + mem[i - 1][j - 1]
return mem[l1][l2]