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
网友评论