不同的子序列(LeetCode-115)

简介: 不同的子序列(LeetCode-115)

不同的子序列(LeetCode-115)


题目

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


字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE" 是 "ABCDE" 的一个子序列,而 "AEC" 不是)


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


示例 1:



示例 2:



提示:


0 <= s.length, t.length <= 1000

s 和 t 由英文字母组成


思路

五部曲


dp[i][j] 含义


以 i − 1 为结尾的字符串s子序列中出现以 j − 1为结尾的字符串t的个数

递推公式


如果 s [ i − 1 ] = t [ j − 1 ]


一种方法是用 s [ i − 1 ]  来匹配,个数为 d p [ i − 1 ] [ j − 1 ]

即使相等,就一定要用它匹配?举个例子 s : b a g g s:bagg,s [ 3 ] = s [ 2 ],可以选着用 s [ 3 ]进行匹配,也可以不选,那就是用 d p [ i − 1 ] [ j ]

如果二者不相等,肯定不能用 s [ i − 1 ] s[i-1]s[i−1],所以 d p [ i ] [ j ] = d p [ i − 1 ] [ j ]


数组初始化


dp[i][0] 表示出现空字符串的个数,只有一种方法,就是全删,所以等于一

dp[0][j] 表示空字符串出现以 j − 1为结尾的字符串t的个数,只能为零

dp[0][0] 空字符串可以删除0个元素,出现空字符串t,所以为一

遍历顺序


从前往后

测试用例



代码展示

class Solution
{
public:
    int numDistinct(string s, string t)
    {
        int n1 = s.size();
        int n2 = t.size();
        if (n1 < n2)
        {
            return 0;
        }
        vector<vector<uint64_t>> dp(n1 + 1, vector<uint64_t>(n2 + 1));
        dp[0][0] = 1;
        for (int i = 0; i < n1; i++)
        {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n1; i++)
        {
            for (int j = 1; j <= n2; 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];
                }
            }
        }
        return dp[n1][n2];
    }
};
目录
相关文章
|
Android开发
【Android构建篇】MakeFile语法中 := 和 = 的区别
使用:= 在Makefile中使用 := 赋值方式定义变量时,如果该变量定义中包含了其他变量的引用,那么这些引用所表示的值将在变量定义时即被展开。也就是说,子变量会被立即展开,并赋值给父变量。
179 0
|
网络安全
ImportError: pycurl: libcurl link-time ssl backend
ImportError: pycurl: libcurl link-time ssl backend
151 0
|
12天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1257 5
|
1天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
11天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1279 87