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

发布时间:2024年01月04日

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
  • 两个字符串都只由小写字符组成。

代码

func isSubsequence(s string, t string) bool {
    n1 := len(s)
    n2 := len(t)
    dp := make([][]int, n1+1)
    for i := 0; i <= n1; i++ {
        dp[i] = make([]int, n2+1)
    }
    for i := 1; i <= n1; i++ {
        for j := 1; j <= n2; j++ {
            if s[i-1] == t[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    if dp[n1][n2] == n1 {
        return true
    }
    return false
}

115. 不同的子序列

困难
相关标签
相关企业
给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数,结果需要对 10(9) + 7 取模。

示例 1:
输入:s = “rabbbit”, t = "rabbit"输出:3
解释:
如下所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
rabbbitrabbbitrabbbit
示例 2:
输入:s = “babgbag”, t = “bag”
输出:5
解释:
如下所示, 有 5 种可以从 s 中得到 “bag” 的方案。
babgbagbabgbagbabgbagbabgbagbabgbag

提示:

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

思路

  • dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
  • 递推公式
  • 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];}
文章来源:https://blog.csdn.net/qq_41735944/article/details/135380374
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。