LeetCode: 392. Is Subsequence

Summary

Return true if string s is a subsequence of string t; otherwise, return false.

A subsequence of a string is a new string formed from the original string by deleting some or none of its characters without changing the relative positions of the remaining characters.

Approach

Use a simple two-pointer check by traversing both strings.

Function

Initialization:

s
t
t_pos: the current traversal position in t

For each character ch in s:

Traverse t until we find ch.
On each step, increment t_pos by 1.
After a match, move to the next character in t for the next search.

If all characters in s are matched in order, return true.

Edge case:

If s is empty, return true.
If t is empty and s is not, return false.

Complexity

Time Complexity: O(S + T), where S is the length of s and T is the length of t. Space Complexity: O(1).

Other Function

Python `iter`

Use Python iteration.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        it = iter(t)
        return all(ch in it for ch in s)

This version uses a generator inside all(...), so the extra space is O(1) (excluding the iterator object).

Recursive

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        def find(s_idx, t_idx):
            if s_idx >= len(s):
                return t_idx <= len(t)
            if t_idx >= len(t):
                return False # s still has unmatched characters, but t is already exhausted.
            # check the current characters.
            if s[s_idx] == t[t_idx]:
                return find(s_idx+1, t_idx+1)
            else:
                return find(s_idx,t_idx+1)
        return find(0, 0)

Time Complexity: O(S + T). Space Complexity: O(S + T) in the worst case due to recursive call stack depth.

Only traverse t

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = 0
        for ch in t:
            if i < len(s) and ch == s[i]:
                i += 1
        return i == len(s)

This has the best complexity: O(T) time and O(1) space.