每日一题之判断子序列

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

判断子序列

题目链接

给定字符串 st ,判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace""abcde"的一个子序列,而"aec"不是)。

示例 1:

输入:s = "abc", t = "ahbgdc"
输出:true

示例 2:

输入:s = "axc", t = "ahbgdc"
输出:false

提示:

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • 两个字符串都只由小写字符组成。

首先,我们定义一个二维布尔数组 dp,其中 dp[i][j] 表示字符串 t 的前 i 个字符是否包含字符串 s 的前 j 个字符作为子序列。我们的目标是求出 dp[t.length()][s.length()]。

动态规划的转移方程如下:

  • 当 s[j] != t[i] 时,dp[i][j] = dp[i-1][j]。这表示如果当前考察的字符 t[i] 和 s[j] 不相等,那么 t 的前 i 个字符是否包含 s 的前 j 个字符作为子序列的结果与 t 的前 i-1 个字符是否包含 s 的前 j 个字符作为子序列的结果相同。

  • 当 s[j] == t[i] 时,我们有两种选择:

    • 我们可以选择使用 t[i] 来匹配 s[j],此时我们需要查看 t 的前 i-1 个字符是否包含 s 的前 j-1 个字符作为子序列,这就是 dp[i-1][j-1]。
    • 我们也可以选择不使用 t[i] 来匹配 s[j],即我们跳过 t[i],查看 t 的前 i-1 个字符是否包含 s 的前 j 个字符作为子序列,这就是 dp[i-1][j]。

    因此,当 s[j] == t[i] 时,dp[i][j] = dp[i-1][j-1] || dp[i-1][j]。如果 t 的前 i-1 个字符包含 s 的前 j-1 个字符作为子序列,或者 t 的前 i-1 个字符包含 s 的前 j 个字符作为子序列,那么 t 的前 i 个字符就包含 s 的前 j 个字符作为子序列。

下面是使用 Python 实现的代码:文章来源地址https://www.toymoban.com/news/detail-604846.html

def isSubsequence(s, t):
    m, n = len(t), len(s)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # 当 s 为空字符串时,它是任何字符串的子序列
    for i in range(m + 1):
        dp[i][0] = True

    for i in range(1, m + 1):
        for j in range(1, min(i + 1, n + 1)):  # j 不能大于 i
            if t[i - 1] == s[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] or dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[m][n]

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

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

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

相关文章

  • 每日一题之最长连续递增序列

    题目链接 给定一个未经排序的整数数组,找到最长且 连续递增的子序列 ,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r ( l r )确定,如果对于每个 l = i r ,都有 nums[i] nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

    2024年02月12日
    浏览(37)
  • (动态规划) 132. 分割回文串 II ——【Leetcode每日一题】

    难度:困难 给你一个字符串 s ,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 示例 1: 输入:s = “aab” 输出:1 解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。 示例 2: 输入:s = “a” 输出:0 示例 3: 输入:

    2024年02月15日
    浏览(45)
  • LeetCode每日一题之 复写0

    目录 题目介绍: 算法原理: 特殊位置处理: 代码实现: 题目链接:. - 力扣(LeetCode) 这种对数组元素进行修改,移动的题目我们仍然可以使用双指针法,不过我们按照常规思路从左到右处理数组,不难发现如下这种问题: 当cur指向1时,让dest下一个元素复写cur指向的元素

    2024年04月23日
    浏览(50)
  • (动态规划) 剑指 Offer 60. n个骰子的点数 ——【Leetcode每日一题】

    难度:中等 把 n 个骰子扔在地上,所有骰子朝上一面的点数之和为 s 。输入 n ,打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。 示例 1: 输入: 1 输出: [0.16667,0.16667,0.16667,

    2024年02月11日
    浏览(41)
  • (动态规划) 剑指 Offer 42. 连续子数组的最大和 ——【Leetcode每日一题】

    难度:简单 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为 O(n) 。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 提示 : 1 = a r r . l e n g t h = 1 0 5 1 = arr.length = 10^

    2024年02月11日
    浏览(49)
  • (动态规划) 剑指 Offer 10- I. 斐波那契数列 ——【Leetcode每日一题】

    难度:简单 写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N) )。斐波那契数列的定义如下: F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N 1. 斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7(1000000007),如计

    2024年02月12日
    浏览(51)
  • 罗勇军 →《算法竞赛·快冲300题》每日一题:“乘积” ← 动态规划

    【题目来源】 http://oj.ecustacm.cn/problem.php?id=1781 http://oj.ecustacm.cn/viewnews.php?id=1023 【题目描述】 给你一个长度为 n 的序列,序列中的元素只包括 1 和 -1。 请问有多少个连续的子序列乘积为正数。 【输入格式】 输入第一行为正整数 n。(n不超过10^6) 第二行包含 n 个整数。 【输

    2024年02月11日
    浏览(49)
  • 【LeetCode每日一题】2645. 构造有效字符串的最少插入数(计算组数+动态规划+考虑相邻字母)

    2024-1-11 2645. 构造有效字符串的最少插入数 方法一:计算组数 1.用count统计,能构成几组abc 2.如果当前字符大于之前字符,说明还在组内,不更新 3.如果当前字符小于等于之前字符,说明不是同一组的abc,组数更新 4.最终返回值:组数*3,再减去原本的字符数,就是要插入的次数

    2024年01月17日
    浏览(58)
  • (动态规划) 剑指 Offer 48. 最长不含重复字符的子字符串 ——【Leetcode每日一题】

    难度:中等 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”,所

    2024年02月11日
    浏览(55)
  • 算法 DAY55 动态规划11 392.判断子序列 115.不同的子序列

    本题可以直接用双指针解法。但是本题是编辑距离的入门题目,故采用动态规划解法为后序“编辑距离”类题目打基础。 本题与最大子序列非常相似,但不同的是s必须连续,t可以不连续。 五部曲 1、dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同

    2024年02月03日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包