给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
采用DP，重点在于状态转移方程。令二维数组distinct_nums[][]，distinct_nums[i][j]表示s[0...j]的子序列中t[0...i]出现的个数。我们可以这样来填充distinct_nums[][]。如果s[j]不等于t[i]，那子串不可能以s[j]结尾，故distinct_nums[i][j] = distinct_nums[i][j - 1]。如果s[j]等于t[i]，那则有两种情况，子串以s[j]结尾(distinct_nums[i - 1][j - 1])或者不以s[j]结尾(distinct_nums[i][j - 1])。总结下来：
distinct_nums[i][j] = distinct_nums[i - 1][j - 1] + distinct_nums[i][j - 1] if s[j] == t[i] else distinct_nums[i][j - 1]
时间空间复杂度均为O(s * t)。
class Solution:
def numDistinct(self, s: str, t: str) -> int:
# cover the edge cases
if t == '':
return 1
if s == '':
return 0
distinct_nums = list()
for _ in range(len(t)):
distinct_nums.append([0] * len(s))
# initialise the first line
for idx in range(len(s)):
if s[idx] == t[0]:
distinct_nums[0][idx] = (distinct_nums[0][idx - 1] + 1) if idx > 0 else 1
else:
distinct_nums[0][idx] = distinct_nums[0][idx - 1] if idx > 0 else 0
# from left to right, top to down, fill the matrix
for i in range(1, len(t)):
for j in range(1, len(s)):
distinct_nums[i][j] = distinct_nums[i][j - 1]
if s[j] == t[i]:
distinct_nums[i][j] += distinct_nums[i - 1][j - 1]
return distinct_nums[-1][-1]
