不同的子序列
- 难度: 困难
- 通过率: 34.1%
- 题目链接:https://leetcode-cn.com/problems/distinct-subsequences
题目描述
给定一个字符串 S 和一个字符串 T,计算在 S 的子序列中 T 出现的个数。
一个字符串的一个子序列是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE"
是 "ABCDE"
的一个子序列,而 "AEC"
不是)
解法:
动态规划
table[i, j]
代表 T 的前 i 个字符,可以由 S 的前 j 个字符构成的个数。
转移方程:
1. 当 S[j] == T[i]
时,S[j]
有两种选择:
-
S[j]
参与构成用于与 T 进行匹配的字串,此时就是为S[:j]
和T[:i]
各拼接了一个相同的字符,因此S[:j+1]
和T[:i+1]
得出的个数,与S[:j]
和T[:i]
得出的个数相同。此个数就等于table[i-1, j-1]
。 -
S[j]
不参与构成字串,此时需要用S[:j]
来构成和T[:i+1]
匹配的子串,个数为table[i, j-1]
。
因此 table[i, j] = table[i-1, j-1] + table[i, j-1]
2. 当 S[j] != T[i]
时:
S[j]
没法参与构成字串,只能依赖于 S[:j]]
来构成和 T[:i+1]
匹配的子串。因此:table[i, j] = table[i, j-1]
举例如下:
图来源于 https://leetcode-cn.com/problems/two-sum/solution/dong-tai-gui-hua-by-powcai-5/
第一行, T 为空串,因为空串是所有字符串子集,且仅有一种可能, 所以第一行都是 1。
第一列, S 为空,这样组成 T 个数自然为 0。
import numpy as np
class Solution:
def numDistinct(self, s: str, t: str) -> int:
table = np.zeros((1 + len(t), 1 + len(s)), dtype=int)
table[:, 0] = 0
table[0] = 1
for i, t_char in enumerate(t, 1):
for j, s_char in enumerate(s, 1):
if s_char == t_char:
table[i, j] = table[i-1, j-1] + table[i, j-1]
else:
table[i, j] = table[i, j-1]
return table[-1,-1]