leetcode with python:392. Is Subsequence

题目:

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

给定两字串s和t,判断s是否是t的subsequence
定义:若一字串a删除一些元素就变为b字串,则称b为a的subsequence

先说我一开始的想法

class Solution:    def isSubsequence(self, s: str, t: str) -> bool:        for i in s:            if i in t:                x=t.index(i)                t=t[x+1:len(t)]            else:                return False        return True

一个一个确认s的字元是否在t内
不在就回传False
在的话就找出其位置(x),将t变为x后的字串
因为要防止元素都在t内,但顺序不一样的可能
最后执行时间32ms(faster than 94.61%)

后来想到双指标也行

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

设立两个指标(i,j),分别从s和t的头开始
j不断往前,i则在j遇到和自己位置一样的值时才往前
直到其中一个指标走到底
若迴圈结束时,若i==len(s),则表示迴圈结束是因为i走到底
也就表示s是t的subsequence,回传True
反之回传False
最后执行时间28ms(faster than 98.23%)

那我们下题见