跳至主要內容

0392. 判断子序列

ITCharge大约 1 分钟

0392. 判断子序列open in new window

  • 标签:双指针、字符串、动态规划
  • 难度:简单

题目链接

题目大意

描述:给定字符串 sstt

要求:判断 ss 是否为 tt 的子序列。

说明

  • 0s.length1000 \le s.length \le 100
  • 0t.length1040 \le t.length \le 10^4
  • 两个字符串都只由小写字符组成。

示例

  • 示例 1:
输入:s = "abc", t = "ahbgdc"
输出:True
  • 示例 2:
输入:s = "axc", t = "ahbgdc"
输出:False

解题思路

思路 1:双指针

使用两个指针 iijj 分别指向字符串 sstt,然后对两个字符串进行遍历。

  • 遇到 s[i]==t[j]s[i] == t[j] 的情况,则 ii 向右移。
  • 不断右移 jj
  • 如果超过 sstt 的长度则跳出。
  • 最后判断指针 ii 是否指向了 ss 的末尾,即:判断 ii 是否等于 ss 的长度。如果等于,则说明 sstt 的子序列,如果不等于,则不是。

思路 1:代码

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

思路 1:复杂度分析

  • 时间复杂度O(n+m)O(n + m),其中 nnmm 分别为字符串 sstt 的长度。
  • 空间复杂度O(1)O(1)