115-不同的子序列(Distinct Subsequences)
发表于：2021-12-03 | 分类： 困难
字数统计: 371 | 阅读时长: 1分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/distinct-subsequences

英文原文

Given two strings s and t, return the number of distinct subsequences of s which equals t.

A string's subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters' relative positions. (i.e., "ACE" is a subsequence of "ABCDE" while "AEC" is not).

The test cases are generated so that 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.
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.
babgbag
babgbag
babgbag
babgbag
babgbag

 

Constraints:

  • 1 <= s.length, t.length <= 1000
  • s and t consist of English letters.

中文题目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

 

示例 1：

输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

 

提示：

  • 0 <= s.length, t.length <= 1000
  • s 和 t 由英文字母组成

通过代码

高赞题解

翻译题意

读懂题目后，用自己的话“翻译”一下题目，有时候会更容易有思路。
题目：求 s 的子序列中 t 出现的个数，blabla…
翻译：在 s 串身上 “挑选” 字符，去匹配 t 串的字符，求挑选的方式数

递归思路

抓住 “选”，s 要照着 t 来挑选，逐字符考察选或不选，分别来到什么状态？

举例，s 为babgbag，t 为bag，末尾字符相同，于是 s 有两种选择：

  1. 用s[s.length-1]去匹配掉t[t.length-1]，问题规模缩小：继续考察babgba和ba
  2. 不这么做，但t[t.length-1]仍需被匹配，于是在babgba中继续挑，考察babgba和bag
    image.png

是否用它去匹配，是两种不同的挑选方式，各自做下去所产生的方式数，相加，是大问题的解。

现在我们拆解出规模小一点的子问题。完善一下，定义出递归函数：

返回：从开头到s[i]的子串中，出现『从开头到t[j]的子串』的次数。
即，从 前者 选字符，去匹配 后者，的方案数。

看了s[i]==t[j]的情况，那s[i]!=t[j]的情况呢？s[i]不匹配t[j]，唯有拿s[i]之前的子串去匹配

现在两种情况下的递归公式都好写了。递归树底部的 base case 呢？

随着递归压栈，子问题规模（子串长度）在变小：

  • 小到 t 变成空串，此时 s 为了匹配它，方式只有1种：什么字符也不用挑（或 s 也是空串，什么都不做就匹配了，方式数也是1）
  • 小到 s 变成空串，但 t 不是，s 怎么也匹配不了 t，方式数为 0

递归函数的参数可以传子串或索引，但用索引描述子问题，不用每次都切割字符串，也更容易迁移到 dp 解法。

未加入记忆化 代码 超时

54 / 62 test cases passed. Status: Time Limit Exceeded

[]
//详细注释见下方 记忆化递归 代码
func numDistinct(s string, t string) int { 
	sLen, tLen := len(s), len(t)

	var helper func(i, j int) int
	helper = func(i, j int) int {
		if j < 0 {  // base case
			return 1
		}
		if i < 0 { // 这两个base case 的顺序不能调换！因为 i<0 且 j<0 时 应该返回1
			return 0
		}
		if s[i] == t[j] {
			return helper(i-1, j) + helper(i-1, j-1)
		} else {
			return helper(i-1, j)
		}
	}
	return helper(sLen-1, tLen-1)
}
[]
var numDistinct = function(s, t) {
	const sLen = s.length, tLen = t.length
	
	function helper(i, j) {
		if (j < 0) {
			return 1
		}
		if (i < 0) {
			return 0
		}
		
		if (s[i] == t[j]) {
			return helper(i-1, j) + helper(i-1, j-1)
		} else {
			return helper(i-1, j)
		}
	}
	return helper(sLen-1, tLen-1) 
};

加入记忆化 代码

image.png

[]
func numDistinct(s string, t string) int {
	sLen, tLen := len(s), len(t)

	memo := make([][]int, sLen) // 二维memo数组 存储计算过的子问题的结果
	for i := range memo {
		memo[i] = make([]int, tLen)
		for j := 0; j < tLen; j++ {
			memo[i][j] = -1
		}
	}
	var helper func(i, j int) int
	helper = func(i, j int) int { // 从开头到s[i]的子串中，出现『从开头到t[j]的子串』的 次数
		if j < 0 { // base case 当j指针越界，此时t为空串，s不管是不是空串，匹配方式数都是1
			return 1
		}
		if i < 0 { // base case i指针越界，此时s为空串，t不是，s怎么也匹配不了t，方式数0
			return 0
		}
		if memo[i][j] != -1 { // memo中有当前遇到的子问题的解，直接拿来返回
			return memo[i][j]
		}
		if s[i] == t[j] { // t[j]被匹配掉，对应helper(i-1, j-1)，不被匹配掉对应helper(i-1, j)
			memo[i][j] = helper(i-1, j) + helper(i-1, j-1)
		} else {
			memo[i][j] = helper(i-1, j) // 
		}
		return memo[i][j] // 返回当前递归子问题的解
	}

	return helper(sLen-1, tLen-1)//从开头到s[sLen-1]的子串中，出现『从开头到t[tLen-1]的子串』的次数
}
[]
var numDistinct = function(s, t) {
	const sLen = s.length, tLen = t.length
	memo = new Array(sLen)
	for (let i = 0; i < sLen; i++) {
		memo[i] = new Array(tLen)
		for (let j = 0; j < tLen; j++) {
			memo[i][j] =  -1
		}
	}
	function helper(i, j) {
		if (j < 0) {
			return 1
		}
		if (i < 0) {
			return 0
		}
		if (memo[i][j] !=  -1) { 
			return memo[i][j]
		}
		if (s[i] == t[j]) {
			memo[i][j] = helper(i-1, j) + helper(i-1, j-1)
		} else {
			memo[i][j] = helper(i-1, j)
		}
		return memo[i][j]
	}
	return helper(sLen-1, tLen-1) 
};

动态规划 与 递归 的区别

其实我们由下面的递归公式，就看出了递推关系——之前的状态推出了 i,j 的状态

if s[i] == t[j] {
	memo[i][j] = helper(i-1, j) + helper(i-1, j-1)
} else {
	memo[i][j] = helper(i-1, j)
}

递归是自上而下调用，子问题自下而上被解决，最后解决了整个问题，而dp是从base case 出发，通过在dp数组记录中间结果，自下而上地顺序地解决子问题。

dp就好像一种不带重复计算的递归，想出dp往往也是像想出递归那样，都需要从子问题入手，正确定义子问题，递归想出结束条件，dp想出base case，递归想出递归公式，dp想出递推公式。递归加入记忆化后，往往稍作修改，就是dp的解法。

dp 解法

dp[i][j]：从开头到s[i-1]的子串中，出现『从开头到t[j-1]的子串』的 次数。即：前 i 个字符的 s 子串中，出现前 j 个字符的 t 子串的次数。
状态转移方程：

  • 当s[i-1] != t[j-1]时，有dp[i][j] = dp[i-1][j]
  • 当s[i-1] == t[j-1]时，有dp[i][j] = dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

base case

  • j==0时，dp[i][0] = 1
  • i==0时，dp[0][j] = 0

dp 代码

image.png

[]
func numDistinct(s string, t string) int {
	sLen, tLen := len(s), len(t)
	// dp[i][j]：前 i 个字符的 s 子串中，出现前 j 个字符的 t 子串的次数
	dp := make([][]int, sLen+1) // 二维dp数组
	for i := range dp {
		dp[i] = make([]int, tLen+1)
	}
	for i := 0; i < sLen+1; i++ {  // 遍历dp矩阵，填表
		for j := 0; j < tLen+1; j++ {
			if j == 0 {			 // base case
				dp[i][j] = 1
			} else if i == 0 {  // base case
				dp[i][j] = 0
			} else {			// 递推公式
				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[sLen][tLen] // 前 sLen 个字符的 s 串中，出现前 tLen 个字符的 t 串的次数
}
[]
var numDistinct = function(s, t) {
	const sLen = s.length, tLen = t.length
	dp = new Array(sLen+1)
	for (let i = 0; i < sLen+1; i++) {
		dp[i] = new Array(tLen+1).fill(0)
	}
	for (let i = 0; i < sLen+1; i++) {
		for (let j = 0; j < tLen+1; j++) {
			if (j == 0) {		
				dp[i][j] = 1
			} else if (i == 0) { 
				dp[i][j] = 0
			} else {			
				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[sLen][tLen]
}

复盘总结

把握住：挑选，既然挑选，就会出现对单个字符的不同选择，作出一种选择后，就变成了一个规模小一点的子问题，是我们要计算的状态，我们找到递推关系。

递归自上而下将问题拆解，然后自下而上逐个解决，dp呢，从base case出发，顺序地一个个计算子问题，像填表格一样。

二者的难点都在于定义递归函数（定义dp子问题），有时候不妨先想想递归，加入记忆化，它解决的子问题个数和dp是一样的，本质上记忆化递归的时间复杂度和dp是一样的。

感谢阅读，写作不易，讲解面向新手，话可能比较多，主要侧重在思路，基本涵盖重难点，希望你没带着疑惑离开。点开题解然后带着疑惑关掉，是一种时间的浪费，这感觉我懂。我不想浪费大家时间，所以浪费自己时间（反复读改），写点东西，练练表达。喜欢的点个赞鼓励一下。

这个二维dp可以降维，评论区已经有人贴出来了。

最后修改于 2021-10-08

统计信息

通过次数 提交次数 AC比率
66489 127704 52.1%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
字符串 动态规划
上一篇:
113-路径总和 II(Path Sum II)
下一篇:
116-填充每个节点的下一个右侧节点指针(Populating Next Right Pointers in Each Node)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo