leetcode做题笔记115. 不同的子序列

这篇具有很好参考价值的文章主要介绍了leetcode做题笔记115. 不同的子序列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数。

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

思路一:动态规划

int numDistinct(char * s, char * t){
    int len1=strlen(s),len2=strlen(t);
    uint64_t dp[len1+1][len2+1];
    memset(dp,0,sizeof dp);
    for(int i=0;i<=len1;i++)
        dp[i][0]=1;
    
    for(int i=1;i<=len1;i++)
    {
        for(int j=1;j<=len2;j++)
      {     
            if(s[i-1]!=t[j-1])
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
        }
    }
    if(dp[len1][len2]>INT_MAX)return -1;
    return dp[len1][len2];
}

分析:

本题要计算t在s子序列的个数,可想到使用动态规划的方法,根据两个字符串的顺序不断向后匹配,当匹配的相同位置字符不相同时调用前面匹配成功的dp[i-1][j],当字符相同时dp[i][j]=dp[i-1][j-1]+dp[i-1][j]最后判断是否大于int范围,返回dp[len1][len2];

总结:

本题考察动态规划在字符串之中的应用,考虑每一位匹配的结果调用前一位的结果即可解决文章来源地址https://www.toymoban.com/news/detail-683582.html

到了这里,关于leetcode做题笔记115. 不同的子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录第五十七天|● 392.判断子序列 ● 115.不同的子序列

    题目: 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,\\\"ace\\\"是\\\"abcde\\\"的一个子序列,而\\\"aec\\\"不是)。 进阶: 如果有大量输入的 S,称作 S1, S2, … , Sk 其中

    2024年02月06日
    浏览(49)
  • 代碼隨想錄算法訓練營|第五十六天|392.判断子序列、1035.不相交的线、115.不同的子序列。刷题心得(c++)

    目录 讀題 392.判断子序列 自己看到题目的第一想法 看完代码随想录之后的想法 115.不同的子序列 看完代码随想录之后的想法 392.判断子序列 - 實作 思路 原始思路 代碼隨想錄思路 Code 原始思路 代碼隨想錄思路 115.不同的子序列 - 實作 思路 Code 總結 自己实现过程中遇到哪些困

    2024年02月06日
    浏览(46)
  • 代码随想录 动态规划 判断子序列,不同的子序列

    392. 判断子序列 给定字符串  s  和  t  ,判断  s  是否为  t  的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如, \\\"ace\\\" 是 \\\"abcde\\\" 的一个子序列,而 \\\"aec\\\" 不是)。 思路: 1. 使用哈希统计两个序

    2024年02月07日
    浏览(45)
  • leetcode做题笔记128. 最长连续序列

    给定一个未排序的整数数组  nums  ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 请你设计并实现时间复杂度为  O(n)   的算法解决此问题。 本题要求最长连续序列,可以将先将数组内数先排序一遍,再向后不断遍历数组比较得到最长连续序列,但

    2024年02月09日
    浏览(43)
  • leetcode做题笔记96. 不同的二叉搜索树

    给你一个整数  n  ,求恰由  n  个节点组成且节点值从  1  到  n  互不相同的  二叉搜索树  有多少种?返回满足题意的二叉搜索树的种数。 本题与上题近似,只需分别考虑左右子树,即f[j-1]*f[i-j]得到状态方程,最后输出f[n[即可,或者直接使用公式,二叉搜索树的种数与

    2024年02月11日
    浏览(37)
  • leetcode做题笔记95. 不同的二叉搜索树 II

    给你一个整数  n  ,请你生成并返回所有由  n  个节点组成且节点值从  1  到  n  互不相同的不同  二叉搜索树   。可以按  任意顺序  返回答案。 本题要列出所有二叉搜索树,即可转换为列举左子树所有集合和右子树所有集合两个问题,分别用递归函数将左右子树根节

    2024年02月11日
    浏览(33)
  • leetcode做题笔记106. 从中序与后序遍历序列构造二叉树

    给定两个整数数组  inorder  和  postorder  ,其中  inorder  是二叉树的中序遍历,  postorder  是同一棵树的后序遍历,请你构造并返回这颗  二叉树  。 本题要利用二叉树的中序遍历和后序遍历来确定二叉树,即可不断创建新二叉树将后序遍历的右子树赋值给新二叉树,不断

    2024年02月11日
    浏览(43)
  • Leetcode 子序列 53 392 115 583

    1.双指针 2.动态规划 初始化: 这里感觉对我来说有点难以理解 dp[i][0] 这里我的理解是,以下标i-1位结尾的s和空集能够相同的子序列的个数,那么肯定只有一个,就是把s里的全部删掉 dp[0][j]s是空数组所以不可能和t一样(除了t是空数组的时候,所以dp[0][0]为1) 注意: 这里不

    2024年02月13日
    浏览(39)
  • LeetCode刷题笔记【30】:动态规划专题-2(不同路径、不同路径 II)

    参考前文 参考文章: LeetCode刷题笔记【29】:动态规划专题-1(斐波那契数、爬楼梯、使用最小花费爬楼梯) LeetCode链接:https://leetcode.cn/problems/unique-paths/description/ 动态规划 : 创建m×n的数组, 对应这个地图, 数组 val 表示 有几种方法可以走到这一格 最开始, 第一行和第一列v

    2024年02月09日
    浏览(60)
  • 【dp】不同的子序列 & 两个字符串的删除操作 & 编辑距离

    dp[i][j]:以j-1为结尾的t出现在以i-1为结尾的s子序列的个数 需要开辟m+1行,n+1列的二维数组 为啥状态方程是: s[i] == t[j] 时 dp[i][j] = dp[i-1][j-1] + dp[i-1][j] s[i] != t[j] 时 dp[i][j] = dp[i-1][j] 先看s[i] == t[j] 时,以s = “rara” t = “ra” 为例,当i = 3, j = 1时,s[i] == t[j] 此时分为2种情况:

    2023年04月15日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包