題目:

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%)

那我們下題見