美文网首页
LeetCode 115. 不同的子序列

LeetCode 115. 不同的子序列

作者: 草莓桃子酪酪 | 来源:发表于2022-08-14 05:06 被阅读0次
题目

给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE" 是 "ABCDE" 的一个子序列,而 "AEC" 不是)
题目数据保证答案符合 32 位带符号整数范围。

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

方法:动态规划
  • dp[i][j] 表示以 i-1 为结尾的字符串 s 中出现以 j-1 为结尾的字符串 t 的个数

  • 初始化

    • dp[0][0] 表示以 -1 为结尾的字符串 s 中出现以 -1 为结尾的字符串 t 的个数,即空字符串中出现空字符串的个数,所以设置为 1
    • dp[i][0] 表示以 i-1 为结尾的字符串 s 中出现以 -1 为结尾的字符串 t 的个数,即以 i-1 为结尾的字符串 s 中出现空字符串的个数,所以设置为 1
    • dp[0][j] 表示以 -1 为结尾的字符串 s 中出现以 j-1 为结尾的字符串 t 的个数,即空字符串为中出现以 j-1 为结尾的字符串 t 的个数,所以设置为 0
  • 外部循环为对字符串 s 的循环,内部循环为对字符串 t 的循环

    • 若两个字符串的字符相同,即 s[i-1] == t[j-1],那么此时的 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],那么此时的 dp[i][j] 为以 i-2 为结尾的字符串 s 中出现以字符串 j-1 为结尾的字符串 t 的个数,即 dp[i-1][j]
class Solution(object):
    def numDistinct(self, s, t):
        dp = [[0] * (len(t)+1) for row in range(len(s)+1)]
        for i in range(len(s)+1):
            dp[i][0] = 1
        for i in range(1, len(s)+1):
            for j in range(1, len(t)+1):
                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[-1][-1]
参考

代码相关:https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html

相关文章

  • LeetCode 115. 不同的子序列

    题目 给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。字符串的一个 子序列 是指,...

  • leetcode 115. 不同的子序列 golang

    不同的子序列 思路 动态规划 dp[i][j]表示S前i个字符 中 T前j个字符的个数。 则有如下递推公式 如果 ...

  • LeetCode 力扣 115. 不同的子序列

    题目描述(困难难度) 给定两个字符串 S 和T,从 S 中选择字母,使得刚好和 T 相等,有多少种选法。 解法一 ...

  • 115. 不同的子序列

    题目描述 distinct-subsequences 给定一个字符串 S 和一个字符串 T,计算在 S 的子序列中...

  • 115. 不同的子序列

    题目描述 给定一个字符串 S 和一个字符串 T,计算在 S 的子序列中 T 出现的个数。一个字符串的一个子序列是指...

  • 115. 不同的子序列

    给定一个字符串 S 和一个字符串 T,计算在 S 的子序列中 T 出现的个数。 一个字符串的一个子序列是指,通过删...

  • 115. 不同的子序列

    给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。字符串的一个 子序列 是指,通过删...

  • python实现leetcode之115. 不同的子序列

    解题思路 使用缓存避免重复计算定义一个函数,计算s的某区间包含t的某区间多少次细节如代码中的注释 115. 不同的...

  • Leetcode 不同的子序列

    题目描述 leecode第115题:不同的子序列[https://leetcode-cn.com/problems...

  • 不同序列dp

    1987. 不同的好子序列数目[https://leetcode-cn.com/problems/number-o...

网友评论

      本文标题:LeetCode 115. 不同的子序列

      本文链接:https://www.haomeiwen.com/subject/zkkxgrtx.html