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)