Problem of The Day: Is Subsequence

Problem Statement

leetcode problem link

Brute Force [Accepted]

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if len(t) < len(s):
            return False

        queue_s = deque(list(s))
        queue_t = deque(list(t))
        len_s = len(s)
        while queue_s:
            c = queue_s.popleft()
            if not queue_t:
                return False
            ch = queue_t.popleft()
            while queue_t and ch != c:
                ch = queue_t.popleft()

            if c == ch:
                len_s -= 1
                if len_s == 0:
                   break

        return len_s == 0

Editorial

Approach 1: Divide and Conquer with Greedy

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        LEFT_BOUND, RIGHT_BOUND = len(s), len(t)

        def rec_isSubsequence(left_index, right_index):
            # base cases
            if left_index == LEFT_BOUND:
                return True
            if right_index == RIGHT_BOUND:
                return False
            # consume both strings or just the target string
            if s[left_index] == t[right_index]:
                left_index += 1
            right_index += 1

            return rec_isSubsequence(left_index, right_index)

        return rec_isSubsequence(0, 0)

Approach 2: Two-Pointers

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        LEFT_BOUND, RIGHT_BOUND = len(s), len(t)

        p_left = p_right = 0
        while p_left < LEFT_BOUND and p_right < RIGHT_BOUND:
            # move both pointers or just the right pointer
            if s[p_left] == t[p_right]:
                p_left += 1
            p_right += 1

        return p_left == LEFT_BOUND