首页 > 其他分享 >115. 不同的子序列(leetcode)

115. 不同的子序列(leetcode)

时间:2024-09-10 16:13:14浏览次数:10  
标签:int 115 空串 序列 leetcode 个字符

https://leetcode.cn/problems/distinct-subsequences/submissions/563375885/

这题比较有难度,具体不太好想到,需要以是否选择s[i]来划分子集
这位描述的很清楚,不做过多赘述

class Solution {
    public int numDistinct(String s, String t) {
        // f[i][j]表示s中前i个字符中选择,有多少个t前j个字符的子串
        // 即s前i个字符中有 f[i][j] 个 t前j个字符 的 子序列
        // 以s第i个字符和t中第j个字符是否相同划分子集
        // 若相同,则意味着 只需要考虑s前i-1个字符中 有多少个 t[0:j-2],即t的前j-1个字符 再加上前面有多少个完整的t,即f[i-1][j]
        // 因为这些都可以 和 最后的 s[i] 一起凑成 t
        // 若不相同,则不需要考虑s的第i个字符了,而是要考虑s的前i-1个字符
        // f[i][j] = if(s[i]==t[j]) f[i-1][j-1] 
        //           else f[i-1][j]
        // f[0][0]=1 // 空串里有一个空串
        // f[0~n][0]=1,f[0][1]=0

        int[][] f=new int[1010][1010];
        for(int i=0;i<=s.length();i++)f[i][0]=1;

        for(int i=1;i<=s.length();i++)
        {
            for(int j=1;j<=t.length();j++)
            {
                if(s.charAt(i-1)==t.charAt(j-1))f[i][j]=f[i-1][j-1]+f[i-1][j];
                else f[i][j]=f[i-1][j];
            }
        }          
        return f[s.length()][t.length()] % 1000000007;         
    }
}

 

标签:int,115,空串,序列,leetcode,个字符
From: https://www.cnblogs.com/lxl-233/p/18406634

相关文章

  • RapidJSON 的坑--允许Object对象存在相同的key,且key为数字时序列化报异常
    RapidJSON的坑--允许Object对象存在相同的key,且key为数字时序列化报异常测试代码如下:1voidshow(rapidjson::Document&doc)2{3printf("-----------------foriterator\nMemberCount:%d\n",doc.MemberCount());4for(autoit=doc.MemberBegin();it!=doc......
  • Leetcode3264. K 次乘运算后的最终数组 I
    EverydayaLeetcode题目来源:3264.K次乘运算后的最终数组I解法1:模拟操作:遍历数组nums,找到其中的最小值x,如果存在多个最小值,选择最前面的一个。将它乘以multiplier。共执行k次操作。代码:/**@lcapp=leetcode.cnid=3264lang=cpp**[3264]K次乘运算......
  • Leetcode3265. 统计近似相等数对 I
    EverydayaLeetcode题目来源:3265.统计近似相等数对I解法1:枚举暴力枚举数组nums中下标i和j满足i<j的nums[i]和nums[j],判断它们是否近似相等。细节:先对数组nums升序排序,在判断它们是否近似相等,转成字符串进行比较,且只交换较大数的数位。代码:/**@l......
  • 【算法题】13.罗马数字转整-力扣(LeetCode)
    【算法题】13.罗马数字转整-力扣(LeetCode)1.题目下方是力扣官方题目的地址13.罗马数字转整数罗马数字包含以下七种字符:I,V,X,L,C,D和M。字符数值I1V5X10L50C100D5......
  • 6、Python如何统计序列中元素的频度
    有一个列表如下:data=['a','c','f','b','f','e','k','d','f','k']如何统计每个元素出现的次数呢?方案一:使用Listcount方法如果只要知道某一个元素出现的次数,直接使用Listcount方法就可以data=['......
  • 类实现序列化接口后自动生成序列化ID
    1、为什么要实现序列化接口?在Java中,Serializable是一个标记接口(markerinterface),它本身并不包含任何方法。当一个类实现了Serializable接口,意味着这个类的对象可以被序列化,即可以转换为字节流,从而可以通过网络传输或者保存到磁盘上。为了保证序列化对象的唯一性以及版本控......
  • Day11 二叉树 part01| LeetCode
    理论基础二叉树的种类满二叉树完全二叉树二叉搜索树平衡二叉搜索树存储方式:数组、链式二叉树的遍历方式深度优先遍历前序(递归法、迭代法)中序(递归法、迭代法)后序(递归法、迭代法)广度优先遍历层序(迭代法)二叉树的定义publicclassTreeNode{......
  • 2389. 和有限的最长子序列
    题目链接2389.和有限的最长子序列思路贪心+排序+二分题解链接非暴力做法:前缀和+二分查找+原地O(1)空间(Python/Java/C++/Go)关键点1.贪心:由于元素和有上限,为了能让子序列尽量长,子序列中的元素值越小越好。2.本题要求计算元素和,因此元素在数组中的位置无......
  • LeetCode题集-3 - 无重复字符的最长子串
    题目:给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。我们先来好好理解题目,示例1中怎么得到长度为3的?如果以第一个字符a为起始,不含重复的最长子串是abc;则我们这样表示(a)bcabcbb->(abc)abcbb,如此表达枚举出所有可能的情况如下:1.(a)bcabcbb->(abc)abcbb;2.a......
  • 946.验证栈序列
    题目链接:leetcode链接思路分析我们知道一个栈的一种入栈顺序可能对应多种出栈顺序,让我们肉眼来判断一下,还是很容易判断出来是不是正确的出栈顺序,那么如何用代码来实现呢?OK,先掏一个栈s出来再说inti=0;先把pushed进一个栈s,然后比较s.top与popped[i],如果相等,就s.p......