392.Is_Subsequence(Easy).md

392. Is Subsequence (Easy)

Date and Time: Jul 8, 2024, (EST)

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

Question:

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.

KeyPoints:

We should check while i < len(s) and j < len(t) at the same time, if one of them is finished, we should return i == len(s). If we don't do that, there may be a case that s[i] is out of bound but the other one is still continue.

Wrong Solution:

These two versions won't work because when s, t have different length it will stop

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # First version
        i, j = 0, 0  # i for s, if i == len(s)
        while j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return False
        
        # Second version
        i = 0
        for j in range(len(t)):
            if i + 1 < len(s) and s[i] == t[j]:
                i += 1
        return i == len(s)

My Solution:

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i, j = 0, 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(n)$
Space Complexity: $O(1)$