leetcode:判断子序列

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

判断子序列

easy

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

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

进阶:

如果有大量输入的 S,称作 S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?

致谢:

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1:

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

示例 2:

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

提示:

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • 两个字符串都只由小写字符组成。
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if len(s) >= len(t):#s长度不小于t
            return s == t 
        
        si = ti = 0#遍历s的指针和t的指针

        while ti < len(t) and si < len(s):
            if t[ti] == s[si]:#从t列表遍历去s中找s[si]对应的字符
                si += 1#si向后移动一位

            ti += 1

        return si == len(s)#如果si移动到最后一位则证明全部找到对应字符

首先,代码检查s的长度是否大于等于t的长度,如果是,则判断s和t是否相等,如果相等则返回True,否则返回False。这是因为如果s的长度大于等于t的长度,但s和t不相等,那么s肯定不是t的子序列。

接下来,代码使用两个指针si和ti进行遍历。si指向s的当前字符,ti指向t的当前字符。在while循环中,如果当前的t字符与s字符相等,si向后移动一位。然后,无论是否相等,ti都向后移动一位。循环继续直到ti达到t的末尾或si达到s的末尾。

最后,代码检查si是否等于s的长度,如果相等,则证明所有的s字符都在t中按顺序出现,返回True,否则返回False。

这段代码的时间复杂度是O(len(t)),其中len(t)表示字符串t的长度。它使用两个指针进行遍历,并在循环中进行字符比较,直到其中一个指针达到末尾位置。

进阶:如果有大量输入的 S,称作 S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # 预处理t,构建字典data_structure
        data_structure = {}
        for i, char in enumerate(t):
            if char not in data_structure:
                data_structure[char] = []
            data_structure[char].append(i)

        # 检查s是否为t的子序列
        prev_pos = -1
        for char in s:
            if char not in data_structure or not any(pos > prev_pos for pos in data_structure[char]):
                return False
            prev_pos = min(pos for pos in data_structure[char] if pos > prev_pos)

        return True

该代码根据优化方案创建了一个字典data_structure,并使用循环遍历字符串t,将字符及其在t中的位置信息存储在字典中。然后,使用另一个循环遍历字符串s,对于每个字符,检查它是否存在于data_structure中,并且存在大于prev_pos的位置,如果满足条件,则更新prev_pos为该位置列表中大于prev_pos的最小值。如果成功遍历完s中的所有字符,返回True,否则返回False

这个优化方案可以大幅减少字符比较的次数,并且更适合处理大量输入的情况。文章来源地址https://www.toymoban.com/news/detail-532877.html

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

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

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

相关文章

  • 算法训练Day55:392.判断子序列 115.不同的子序列

    Category Difficulty Likes Dislikes ContestSlug ProblemIndex Score algorithms Easy (52.43%) 858 0 - - 0 Tags Companies 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如, \\\"ace\\\" 是 \\\"abcde\\\" 的

    2024年02月05日
    浏览(36)
  • Leetcode376. 摆动序列

    题目来源:376. 摆动序列 约定: 某个序列被称为「上升摆动序列」,当且仅当该序列是摆动序列,且最后一个元素呈上升趋势。 某个序列被称为「下降摆动序列」,当且仅当该序列是摆动序列,且最后一个元素呈下降趋势。 特别地,对于长度为 1 的序列,它既是「上升摆动

    2024年02月09日
    浏览(32)
  • leetcode 376. 摆动序列

            本题思路是定义一个 direct变量记录上一次摆动是上坡还是下坡 。 然后在一个for循环中循环判断当前摆动和上一次摆动是否一致,如果不一致则视为一次摆动。 如果前后元素值相等得话,直接continue进入下一次循环。         下面看代码:

    2024年02月15日
    浏览(35)
  • LeetCode128.最长连续序列

     我这个方法有点投机取巧了,题目说时间复杂度最多O(n),而我调用了Arrays.sort()方法,他的时间复杂度是n*log(n),但是AC了,这样的话这道题还是非常简单的,创建一个Hashmap,以nums数组的元素作为key,以这个元素是连续序列中的第几个作为value,先把数组排一下序,然后从第

    2024年02月12日
    浏览(29)
  • 【Leetcode】128.最长连续序列

    给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例1: 示例2: 提示 : 0 = nums.length = 10 5 -10 9 = nums[i] = 10 9

    2024年02月10日
    浏览(63)
  • leetcode300. 最长递增子序列 子序列(不连续)

    https://leetcode.cn/problems/longest-increasing-subsequence/ 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 LIS即最长上升子序列,指

    2024年02月14日
    浏览(41)
  • leetcode 234.判断链表是否为回文

    给定一个单链表,判断它是否是回文。 输入: 1-2 输出: false 输入: 1-2-2-1 输出: true 判断链表是否为回文,可以通过翻转链表后半部分并比较两半部分是否相同来实现。具体步骤如下: 使用快慢指针找到链表的中间节点。 翻转链表的后半部分。 比较前半部分和翻转后的后半部

    2024年01月19日
    浏览(34)
  • leetCode 376.摆动序列 贪心算法

    如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为  摆动序列 。 第一个差(如果存在的话)可能是正数或负数。 仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如,  [1, 7, 4, 9, 2, 5]  是一个  摆动序列  ,因为差值  (6, -3, 5, -7, 3)  是正负

    2024年02月07日
    浏览(38)
  • Leetcode1143. 最长公共子序列

    解题思路 求两个数组或者字符串的最长公共子序列问题,肯定是要用动态规划的。下面的题解并不难,你肯定能看懂。 首先,区分两个概念:子序列可以是不连续的;子数组(子字符串)需要是连续的; 另外,动态规划也是有套路的:单个数组或者字符串要用动态规划时,

    2024年01月25日
    浏览(44)
  • leetcode:递增的三元子序列

    题解部分转自leetcode:Xzz medium 给你一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。 如果存在这样的三元组下标 (i, j, k) 且满足 i j k ,使得 nums[i] nums[j] nums[k] ,返回 true ;否则,返回 false 。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 5 * 105 -231 = nu

    2024年02月13日
    浏览(33)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包