392. Is Subsequence

https://leetcode.com/problems/is-subsequence/

Python

Queue Pop

N = len(s), M = len(t)

• Time: O(M)
• Space: O(N)

from collections import deque


class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        checks = deque(s)
        for char in t:
            if not checks:
                return True

            if checks[0] == char:
                checks.popleft()

        return not bool(checks)

Pointer

N = len(s), M = len(t)

• Time: O(M)
• Space: O(1)

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if not s:
            return True

        i = 0
        for letter in t:
            if i == len(s):
                return True
            if s[i] == letter:
                i += 1

        return i == len(s)