李碧涵.md

392. Is Subsequence

题目描述

给定字符串s和字符串t，判断s是否是t的子序列。

子序列：删除原始字符串的某些字符，不改变相对位置顺序。（例如，"ace" 是"abcde" 的子串，而 "aec" 不是） 假设s和t中只有小写英文字母，len(t) <= 500000且len(s) <= 100

例子

Example 1: s = "abc", t = "ahbgdc" Return true.

Example 2: s = "axc", t = "ahbgdc" Return false.

思想 双下标法

解法

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

简洁

class Solution(object):
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if not s:
            return True
        
        idx = 0
        for c in t:
            if s[idx] == c:
                idx += 1
            if idx == len(s):
                return True
        return False