392. Is Subsequence

Approach 1: Iterate over long string

class Solution(object):
def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
slen, tlen = len(s), len(t)
if slen == 0:
return True
sindex = 0
for i in range(tlen):
if t[i] == s[sindex]:
sindex += 1
if sindex >= slen:
return True
continue
return False

We will iterate over the longer string and every time we see the next character from the short string we will increment the counter. If the counter becomes greater than the length of the shorter string at any point during the long string we return True

Time Complexity: O(len(t))

Space Complexity: O(1)

Approach 2: Iterate over short string

class Solution(object):
def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
index = 0
for c in s:
index = t.find(c,index)
if index == -1:
return False
index += 1
return True

This way we are looking for the next character from s each time, if we find it we move to the next character and so on. If we don't find the next character anywhere after the previous index we will just return False. If we do end up finding the entire string we will return True

Time Complexity: O(len(s))

Space Complexity: O(1)