Is Subsequence
Description
Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence is formed by deleting some (or no) characters from t without changing the relative order of remaining characters.
Example 1:
Input: s = "abc", t = "ahbgdc"
Output: true
Explanation: "abc" is a subsequence: a_b___c matches "ahbgdc".
Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false
Explanation: Cannot find 'x' in correct position in t.
Example 3:
Input: s = "", t = "ahbgdc"
Output: true
Explanation: Empty string is a subsequence of any string.
Constraints
0 <= s.length <= 1000 <= t.length <= 10^4s and t consist only of lowercase English letters
Complexity
Show Complexity
- Time:
O(n) - Space:
O(1)
Hints
Show Hints
- Pattern
- Use two pointers: one for each string
- Approach
- Move through t, advance s pointer only when characters match. Return true if s pointer reaches end.
- Complexity
- Single pass through t is enough - O(n) where n = len(t)
Solutions
Show PY Solution
def solution(s, t):
i = 0
j = 0
if len(s) == 0:
return True
n2 = len(t)
while j < n2:
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)