Is Subsequence#

Levels: level-2

Data structures: string

Patterns: two-pointers

Practice Link#

LeetCode

Description#

Given two strings s (source) and t (target), return True if t is a subsequence of s, else False.
Order must be preserved.
Edge cases:
- ("", "") -> True
- ("abcd", "") -> True
- ("", "a") -> False

Examples#

1("abcd", "bd") -> True
2("abcd", "be") -> False

Python Solution#

 1def is_subsequence(s: str, t: str) -> bool:
 2    """
 3    Returns True if t is a subsequence of s.
 4
 5    Time:  O(len(s))
 6    Space: O(1)
 7    """
 8    i = 0  # pointer in t
 9    for ch in s:
10        if i < len(t) and ch == t[i]:
11            i += 1
12            if i == len(t):
13                return True
14    return i == len(t)