问题

给定两个字符串，s 和 t，判断s是不是t的一个子序列

s = "abc", t = "ahbgdc"
Return true
s = "axc", t = "ahbgdc"
Return false.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路

两个指针移动，如果相等s和t都移动一步，不相等则t移动一步，最后如果s移动到最后，则说明s是t的一个子序列。

时间复杂度O(n)，空间复杂度O(1)

代码

class Solution(object):
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if(s==''):
            return True
        if(t==''):
            return False
        i = 0
        j = 0
        while j<len(t) and i<len(s):
            if(t[j] == s[i]):
                i += 1
            j += 1
        return i == len(s)

类似题目

115. Distinct Subsequences

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄