115. 不同的子序列

迈不过友情╰ 2023-09-30 09:16 20阅读 0赞

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

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

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

示例1：

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

输入：s = “babgbag”, t = “bag”  
输出：5  
解释：  
如下图所示, 有 5 种可以从 s 中得到 “bag” 的方案。  
babgbag  
babgbag  
babgbag  
babgbag  
babgbag

提示：

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/distinct-subsequences  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

回溯不带path的

/**
     * @param {string} s
     * @param {string} t
     * @return {number}
     */
    var numDistinct = function(s, t) {
        // 回溯
        let res = 0
        let backtrack = function(k, n) {
            if (n === t.length) {
                res++;
                return
            }
            for (let i = k; i < s.length; i++) {
                if (s[i] === t[n]) {
                    backtrack(i+1, n+1);
                }
            }
        }
        backtrack(0, 0);
        return res;
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，20人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|动态规划No.22】leetcode115. 不同的子序列

【算法|动态规划No.22】leetcode115. 不同的子序列

Love The Way You Lie/ 2024年04月27日 06:41/ 0 赞/ 77 阅读

相关 940. 不同的子序列 II

940. 不同的子序列 II 问题：给定一个字符串 s，计算 s 的不同非空子序列的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余。字符串的

短命女/ 2024年04月03日 13:05/ 0 赞/ 67 阅读

相关 LeetCode-115. 不同的子序列

目录动态规划题目来源 [115. 不同的子序列][115.] 动态规划 1.确定dp数组（dp table）以及下标的含义 dp\[

快来打我*/ 2024年03月24日 10:04/ 0 赞/ 36 阅读

相关【算法挨揍日记】day38——115. 不同的子序列、44. 通配符匹配

115. 不同的子序列 [115. 不同的子序列][115.] 题目描述：给你两个字符串 `s`和 `t` ，统计并返回在 `s` 的子序列中 `t` 出现

朴灿烈づ我的快乐病毒、/ 2024年02月05日 12:56/ 0 赞/ 62 阅读

相关 115. 不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的

迈不过友情╰/ 2023年09月30日 09:16/ 0 赞/ 21 阅读

相关 LeetCode动态规划子序列问题——115.不同的子序列

题目描述： [115. 不同的子序列![icon-default.png_t_M4AD][]https://leetcode.cn/problems/distinct-s

今天药忘吃喽~/ 2023年09月28日 10:16/ 0 赞/ 28 阅读

相关 C语言重构【115】不同的子序列

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

淩亂°似流年/ 2022年12月21日 10:50/ 0 赞/ 138 阅读

相关 LeetCode 115. 不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的

野性酷女/ 2022年10月22日 14:57/ 0 赞/ 175 阅读

相关 leetcode 115. Distinct Subsequences Hard | 115. 不同的子序列（动态规划）

题目 [https://leetcode.com/problems/distinct-subsequences/][https_leetcode.com_problems

约定不等于承诺〃/ 2022年10月18日 15:49/ 0 赞/ 73 阅读

相关 leetcode 115. 不同的子序列

递归超时唉 include <iostream> include <string> include <vector> using names

r囧r小猫/ 2022年02月05日 12:39/ 0 赞/ 157 阅读