【Python3】【力扣题】392. 判断子序列

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

【力扣题】题目描述:

【Python3】【力扣题】392. 判断子序列,力扣题,leetcode,python

【Python3】代码:

1、解题思路:遍历字符串s,使用一个列表依次记录在字符串t中的位置,若没有该字母则返回False,若索引号小于上一个字母的索引号,返回False。否则返回True。

知识点:[ ]:创建新列表。相当于 list()。

              字符串.find(...):在字符串中查找某元素,返回索引号,没有返回-1。

              列表[-1]:获取列表中最后一个元素。

              列表.append(...):往列表尾部添加一个元素。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        alist = []
        i = -1
        for x in s:
            i = t.find(x,i+1)
            if i == -1: return False
            if alist and i <= alist[-1]:
                return False
            alist.append(i)
        return True

也可以用两个队列分别记录字符串s和t,遍历字符串s,依次从t的队列队头移除一个元素,若与s的字母相同,s的队列队头移除该元素,最终s的队列没有元素,则返回True,否则返回False。

知识点:collections.deque(...):双端队列。左端进,右端出。也可以右端进,左端出。

              队列.popleft():从队列的队头(左端)移除一个元素,并返回该元素。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        from collections import deque
        sdeque, tdeque = deque(s), deque(t)
        for x in s:
            while tdeque:
                if x == tdeque.popleft():
                    sdeque.popleft()
                    break
        return not sdeque

也可以遍历字符串t,依次判断是否与字符串s中的字母相同。若字符串t遍历完,字符串s仍有字母,则返回False,否则返回True。

知识点:字符串[索引]:获取字符串中索引号对应的元素。

              字符串[起始索引 结束索引]:获取字符串中起始索引(含)到结束索引(不含)的元素。

              len(...):获取序列的长度。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        for x in t:
            if s and x == s[0]:
                s = s[1:]
        return not s
        # 或者
        i, n = 0, len(s)
        for x in t:
            if i < n and x == s[i]:
                i += 1
        return i == n

2、解题思路:双指针。两个指针分别指向两个字符串的起始位置,比对两字母是否相同,若相同,同时指向下一个,若不同,只有字符串t的指针指向下一个。若字符串t遍历完,字符串s仍有字母,则返回False,否则返回True。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i, j = 0, 0
        n, m = len(s), len(t)
        while i < n and j < m:
            if t[j] == s[i]:
                i += 1
            j += 1
        return i == n

3、解题思路:动态规划。

① 获取字符串t的长度m,一个m+1行26列的矩阵(最后一行的内容都为m)。

② 1行对应字符串t的1个元素,26列依次对应26个字母。从后往前遍历字符串t,每一个字母对应的位置记录其在字符串t中的索引号,该行其他列等于下一行该列的内容(例如:字符串t第2个元素为c,则矩阵中行号为1列号为2中内容为1,该行其他列为下一行的内容,注意索引号从0开始)。

【Python3】【力扣题】392. 判断子序列,力扣题,leetcode,python

③ 遍历字符串s,第一个字母从第一行开始找,字母对应位置中内容若为m,则字符串t中不存在该字母返回False,若不为m,则该位置中内容+1作为下一个字母查找的行号,全部查找完,则返回True。

知识点:ord(...):将字符转为ASCII或者Unicode数值。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        m = len(t)
        f = [[0] * 26 for i in range(m)]
        f.append([m] * 26)
        for i in range(m-1,-1,-1):
            for j in range(26):
                f[i][j] = i if j == ord(t[i]) - ord("a") else f[i+1][j]
        add = 0
        for x in s:
            index = ord(x) - ord("a")
            if f[add][index] == m: return False
            add = f[add][index] + 1
        return True

4、解题思路:迭代器。将字符串t转为迭代器,遍历字符串s,所有字母都在该迭代器中则返回True,否则返回False。

知识点:iter(...):转为迭代器。迭代器中元素只依次访问一次。

              all(...):所有都满足条件,则返回True,否则返回False。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        a = iter(t)
        return all(x in a for x in s)

 5、解题思路:使用正则表达式查找。

知识点:".*".join(s):相当于将字符串s中每个内容中间添加.*。例如:【Python3】【力扣题】392. 判断子序列,力扣题,leetcode,python

              re.search(...):使用正则表达式查找某字符串,其中正则表达式".*" 匹配0个或多个任意字符(除了换行符\n)。

                __import__(...):动态加载类和函数。如果一个模块经常变化就可以使用 __import__() 来动态载入。

              bool(...):转为布尔类型,只有True和False。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        return bool(__import__("re").search(".*".join(s), t))
        # 或者
        import re
        res = re.search(".*".join(s), t)
        return bool(res)

 文章来源地址https://www.toymoban.com/news/detail-806248.html

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

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

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

相关文章

  • 算法 DAY55 动态规划11 392.判断子序列 115.不同的子序列

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

    2024年02月03日
    浏览(36)
  • 【代码随想录刷题记录】 392.判断子序列 、 115.不同的子序列

    1、题目 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,\\\"ace\\\"是\\\"abcde\\\"的一个子序列,而\\\"aec\\\"不是)。 题目链接:https://leetcode.cn/problems/is-subsequence/ 2、代码

    2024年02月16日
    浏览(45)
  • 代码随想录第五十七天|● 392.判断子序列 ● 115.不同的子序列

    题目: 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,\\\"ace\\\"是\\\"abcde\\\"的一个子序列,而\\\"aec\\\"不是)。 进阶: 如果有大量输入的 S,称作 S1, S2, … , Sk 其中

    2024年02月06日
    浏览(49)
  • Leetcode 子序列 53 392 115 583

    1.双指针 2.动态规划 初始化: 这里感觉对我来说有点难以理解 dp[i][0] 这里我的理解是,以下标i-1位结尾的s和空集能够相同的子序列的个数,那么肯定只有一个,就是把s里的全部删掉 dp[0][j]s是空数组所以不可能和t一样(除了t是空数组的时候,所以dp[0][0]为1) 注意: 这里不

    2024年02月13日
    浏览(39)
  • 代碼隨想錄算法訓練營|第五十六天|392.判断子序列、1035.不相交的线、115.不同的子序列。刷题心得(c++)

    目录 讀題 392.判断子序列 自己看到题目的第一想法 看完代码随想录之后的想法 115.不同的子序列 看完代码随想录之后的想法 392.判断子序列 - 實作 思路 原始思路 代碼隨想錄思路 Code 原始思路 代碼隨想錄思路 115.不同的子序列 - 實作 思路 Code 總結 自己实现过程中遇到哪些困

    2024年02月06日
    浏览(46)
  • 力扣:60. 排列序列(Python3)

    给出集合  [1,2,3,...,n] ,其所有元素共有  n!  种排列。 按大小顺序列出所有排列情况,并一一标记,当  n = 3  时, 所有排列如下: \\\"123\\\" \\\"132\\\" \\\"213\\\" \\\"231\\\" \\\"312\\\" \\\"321\\\" 给定  n  和  k ,返回第  k  个排列。 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成

    2024年02月13日
    浏览(31)
  • 力扣(Leetcode)——python3

    目录 动态规划 70、爬楼梯 198、打家劫舍 213、打家劫舍Ⅱ  509、斐波那契数 740、删除并获得点数 746、使用最小花费爬楼梯 1137、第N个泰波那契序列 Dynamic Programming 递归+迭代 力扣 https://leetcode.cn/problems/jump-game-ii/ 给你一个非负整数数组 nums ,你最初位于数组的第一个位置。

    2024年02月03日
    浏览(43)
  • leetcode:2717. 半有序排列(python3解法)

    给你一个下标从  0  开始、长度为  n  的整数排列  nums  。 如果排列的第一个数字等于  1  且最后一个数字等于  n  ,则称其为  半有序排列  。你可以执行多次下述操作,直到将  nums  变成一个  半有序排列  : 选择  nums  中相邻的两个元素,然后交换它们。 返回使

    2024年01月24日
    浏览(45)
  • leetcode:1470. 重新排列数组(python3解法)

            给你一个数组  nums  ,数组中有  2n  个元素,按  [x1,x2,...,xn,y1,y2,...,yn]  的格式排列。 请你将数组按  [x1,y1,x2,y2,...,xn,yn]  格式重新排列,返回重排后的数组。 示例 1: 示例 2: 示例 3: 提示: 1 = n = 500 nums.length == 2n 1 = nums[i] = 10^3  

    2024年02月16日
    浏览(43)
  • leetcode:412. Fizz Buzz(python3解法)

    给你一个整数  n  ,找出从  1  到  n  各个整数的 Fizz Buzz 表示,并用字符串数组  answer ( 下标从 1 开始 )返回结果,其中: answer[i] == \\\"FizzBuzz\\\"  如果  i  同时是  3  和  5  的倍数。 answer[i] == \\\"Fizz\\\"  如果  i  是  3  的倍数。 answer[i] == \\\"Buzz\\\"  如果  i  是  5  的倍数。

    2024年02月02日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包