0115. 不同的子序列 #
- 标签:字符串、动态规划
- 难度:困难
题目大意 #
描述:给定两个字符串 s
和 t
。
要求:计算在 s
的子序列中 t
出现的个数。
说明:
- 字符串的子序列:通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,
"ACE"
是"ABCDE"
的一个子序列,而"AEC"
不是)。 - $0 \le s.length, t.length \le 1000$。
s
和t
由英文字母组成。
示例:
|
|
$\underline{rabb}b\underline{it}$ $\underline{ra}b\underline{bbit}$ $\underline{rab}b\underline{bit}$
解题思路 #
思路 1:动态规划 #
1. 划分阶段 #
按照子序列的结尾位置进行阶段划分。
2. 定义状态 #
定义状态 dp[i][j]
表示为:以第 i - 1
个字符为结尾的 s
子序列中出现以第 j - 1
个字符为结尾的 t
的个数。
3. 状态转移方程 #
双重循环遍历字符串 s
和 t
,则状态转移方程为:
- 如果
s[i - 1] == t[j - 1]
,则:dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
。即dp[i][j]
来源于两部分:- 使用
s[i - 1]
匹配t[j - 1]
,则dp[i][j]
取源于以i - 2
为结尾的s
子序列中出现以j - 2
为结尾的t
的个数,即dp[i - 1][j - 1]
。 - 不使用
s[i - 1]
匹配t[j - 1]
,则dp[i][j]
取源于以i - 2
为结尾的s
子序列中出现以j - 1
为结尾的t
的个数,即dp[i - 1][j]
。
- 使用
- 如果
s[i - 1] != t[j - 1]
,那么肯定不能用s[i - 1]
匹配t[j - 1]
,则dp[i][j]
取源于dp[i - 1][j]
。
4. 初始条件 #
dp[i][0]
表示以i - 1
为结尾的s
子序列中出现空字符串的个数。把s
中的元素全删除,出现空字符串的个数就是1
,则dp[i][0] = 1
。dp[0][j]
表示空字符串中出现以j - 1
结尾的t
的个数,空字符串无论怎么变都不会变成t
,则dp[0][j] = 0
dp[0][0]
表示空字符串中出现空字符串的个数,这个应该是1
,即dp[0][0] = 1
。
5. 最终结果 #
根据我们之前定义的状态,dp[i][j]
表示为:以第 i - 1
个字符为结尾的 s
子序列中出现以第 j - 1
个字符为结尾的 t
的个数。则最终结果为 dp[size_s][size_t]
,将其返回即可。
思路 1:动态规划代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n^2)$。两重循环遍历的时间复杂度是 $O(n^2)$,所以总的时间复杂度为 $O(n^2)$。
- 空间复杂度:$O(n^2)$。用到了二维数组保存状态,所以总体空间复杂度为 $O(n^2)$。