Is Subsequence - Leetcode Solution

Problem Statement:

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

Example 1: Input: s = "abc", t = "ahbgdc" Output: true

Example 2: Input: s = "axc", t = "ahbgdc" Output: false

Solution:

First, we need to create two pointers - one for the string s and one for the string t. We'll start at the beginning of both strings and move the pointers as we compare characters. We can do this by using a simple while loop.

def isSubsequence(s: str, t: str) -> bool:
    # create pointers for both strings
    s_pointer = 0
    t_pointer = 0

    # loop until we reach the end of the subsequence or the string
    while s_pointer < len(s) and t_pointer < len(t):
        # compare the current characters
        if s[s_pointer] == t[t_pointer]:
            # if they match, move the subsequence pointer
            s_pointer += 1
        # always move the string pointer
        t_pointer += 1

    # if the s_pointer has reached the end of the subsequence, return True
    return s_pointer == len(s)

Explanation:

In the above code snippet, we have created two pointers - s_pointer and t_pointer to keep track of the current character we're comparing for both the strings s and t. During the loop, we keep comparing the characters until we reach the end of either the s string or the t string.

If the characters match, we move the s_pointer to the next character. Regardless of whether the characters match, we always move the t_pointer to the next character. This makes sure that we explore all possible characters in t.

Finally, we check if the s_pointer points to the end of the s string. If it does, we can return True because that means all the characters in s are present in t, and in the same order.

Conclusion:

The isSubsequence function takes constant space and linear time. It simply compares characters and returns True if all the characters in s are found in the same order in t.

1