算法题--求字符串s的子序列为t的可能情况数

image.png

0. 链接

题目链接

1. 题目

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).

It's guaranteed 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.
(The caret symbol ^ means the chosen letters)

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.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

2. 思路1: 动态规划

• 看到两个字符串, 涉及子序列匹配, 目标问题又是求一个数值, 不假思索开始套动态规划
• 用按照以终为始的思路, 求s的子序列为t, 则s和t的长度就是状态, 目标问题就是s和t都取全部长度, 那么子问题自然就是s左边若干个字符和t左边若干个字符的子序列匹配问题
• 定义状态: dp[i][j]表示s[0:i]和t[0:j]的匹配可能情况数
• 状态转移方程

对于i = 1~m, j = 1~n
如果s[i - 1] == t[j - 1]:
    则dp[i][j]的可能情况数, 可以按照互斥条件分成两大类:
    (1) dp[i - 1][j - 1], 表示s[0:i - 1]和t[0:j - 1]的可能情况数, 即s中第i - 1个字符之前的部分和t中第j - 1个字符之前的部分的匹配情况;
    (2) dp[i - 1][j], 表示s[0:i-1]和t[0:j]的可能情况数, 意味着s的第i-1个字符之前的部分和t的第j个字符之前的部分的匹配情况
    
    (1)和(2)是两种独立的情况, 它们共同构成了dp[i][j]的可能来历
否则
    说明s[i - 1]的加入, 并未改变s前面部分和t前面部分的匹配情况, 也就是说
    dp[i][j] = dp[i - 1][j]

• 初始条件

dp[0][0] = dp[1][0] = ... = dp[m][0] = 1
表示s的前面任意个字符, 和t的空字符的匹配可能性都为1, 直观想法就是因为空字符可以和任何字符匹配

dp[0][1] = dp[0][2] = ... = dp[0][n] = 0
表示s中不取任意字符的结果和t前面任意非0个字符的匹配可能性都为0, 直观想法是非空字符串不可能是空字符串的子序列

• 返回结果 dp[m][n]
• 时间复杂度 O(m*n)
• 空间复杂度 O(m*n)

3. 代码

# coding:utf8


class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m = len(s)
        n = len(t)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = 1
        for i in range(1, m + 1):
            dp[i][0] = 1
        for j in range(1, n + 1):
            dp[0][j] = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j]
        return dp[m][n]


solution = Solution()
print(solution.numDistinct('rabbbit', 'rabbit'))
print(solution.numDistinct('babgbag', 'bag'))

输出结果

3
5

4. 结果

image.png