Please see github.com/anusha-murali for all of my repositories.
Problem:
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
Solution
This is an easy character matching problem that can be solved using two pointers.
We use the first pointer, sp
to iterate through the string s
.
We use the second pointer, tp
to iterate through the string t
.
def isSubsequence(s, t):
sp = tp = 0
while sp < len(s) and tp < len(t):
if s[sp] == t[tp]:
sp += 1
tp += 1
return sp == len(s)
When we exit the while
loop, if sp
is equal to the length of s
, then we have successfully matched all the characters of s
in t
in the same order of their appearance in s
.
Runtime: Runtime is $O(n)$, where $n$ is the length of the longer string. The space complexity is $O(1)$.