代码随想录算法训练营第五十四天 | 115.不同的子序列，392.判断子序列

标签：fori babgbag ++ 随想录 len 115 序列 dp

392. 判断子序列

  已解答 简单  

相关标签

相关企业  

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

 

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

 

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

 

---

package main

 

func isSubsequence(s string, t string) bool { // dp[i][j] s的i t的j 这两位置 是否是子序列 // 递推公式， s[i] == t[j] dp[i][j] = dp[i-1][j-1] else dp[i][j] = dp[i][j-1] // 初始化 dp[0] 0行 全为1 // 从1到end // 输出 dp := make([][]bool, len(s)+1) fori := 0; i < len(dp); i++ { dp[i] = make([]bool, len(t)+1) } fori := 0; i < len(t)+1; i++ { dp[0][i] = true } fori := 1; i < len(s)+1; i++ { forj := 1; j < len(t)+1; j++ { if s[i-1] == t[j-1] { dp[i][j] = dp[i-1][j-1] } else { dp[i][j] = dp[i][j-1] } } } return dp[len(s)][len(t)] }

 

---

115. 不同的子序列

  已解答 困难  

相关标签

相关企业  

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10⁹ + 7 取模。

 

示例 1：

输入：

输出

：

3

解释：

"rabbit" 的方案

rabbbit

rabbbit

rabbbit

示例 2：

输入：

输出

：

5

解释：

"bag" 的方案

babgbag

babgbag

babgbag

babgbag

babgbag

 

提示：

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

 

---

package main

 

func numDistinct(s string, t string) int { //dp[i][j] s的i t的j 不同子序列 这个位置的子序列个数 //递推公式 s[i] = t[j] dp[i][j] = dp[i-1][j-1]+dp[i][j-1] else dp[i][j] = dp[i][j-1] //初始化 0行为为1 //上到下，左到右 //输出 mod := 1000000007 dp := make([][]int, len(t)+1) fori := 0; i < len(dp); i++ { dp[i] = make([]int, len(s)+1) } fori := 0; i < len(s)+1; i++ { dp[0][i] = 1 } fori := 1; i < len(t)+1; i++ { forj := 1; j < len(s)+1; j++ { if t[i-1] == s[j-1] { dp[i][j] = (dp[i-1][j-1] + dp[i][j-1]) % mod } else { dp[i][j] = (dp[i][j-1]) % mod } } } return dp[len(t)][len(s)] }

标签：fori,babgbag,++,随想录,len,115,序列,dp
From： https://www.cnblogs.com/suxinmian/p/18089487