392.Is_Subsequence(Easy).md

392. Is Subsequence (Easy)

Date and Time: Jul 8, 2024 (EST)

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

Question:

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

Edge case 1:

Input: s = "", t = "a"

Output: true

Edge case 2:

Input: s = "", t = ""

Output: true

Edge case 2:

Input: s = "a", t = ""

Output: false

Constraints:

• 0 <= s.length <= 100

• 0 <= t.length <= 10^4

• s and t consist only of lowercase English letters.

Walk-through:

while i < len(s) and j < len(t) we compare s[i], t[j] if they are match we advance i pointer, we also advance j pointer no matter if there is a match or not. When i or j is out of bound, we should check i == len(s) so we know were able to match all s in t.

Attention
Edge case when s = "".

My Solution:

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # i, j pointers to represent s, t
        # if they both match, advance i, j pointers
        # if not match, advance j pointer
        # when i or j are out of bound, check if i == len(s)

        # TC: O(m+n), SC: O(1)
        i = j = 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == len(s)

Time Complexity: $O(m + n)$, m, n are the lengths of s, t.
Space Complexity: $O(1)$