Return true if s is a subsequence of t — that is, s can be formed by deleting
zero or more characters from t without reordering the rest.
isSubsequence(s, t)
Input format: s | t.
s="abc", t="ahbgdc" // → true
s="axc", t="ahbgdc" // → false
s="", t="abc" // → true
s is a subsequence of t if you can find all of s's characters inside t, in order, but not necessarily consecutively — skipping characters in t is allowed. The question is how to check this without trying every way of choosing which characters to skip, since that grows exponentially with t's length.
A naive approach might generate every way s could be embedded in t and check each. Overkill — a subsequence match, if it exists, can always be built by a simple, purely local rule.
To check if s is a subsequence of t, you never need to look ahead or backtrack. Walk t left to right with one pointer, keeping a second pointer on the next character of s you still need. Every time t's current character matches what s is waiting for, advance the s pointer. Otherwise, just move on — skipping costs nothing.
This greedy "take the earliest possible match" is provably correct: matching a needed character as early as possible in t can never hurt, since it leaves the maximum remainder of t available for the rest of s. There's never an advantage to skipping a valid match hoping for a better one later.
Both pointers only move forward, so the whole check is a single pass through t, touching each character at most once — time proportional to t's length, with only two positions as extra memory.
If the s pointer reaches the end of s, every character was matched in order — s is a subsequence. If t runs out first, some character of s was never found — false. This one-pass, two-pointer greedy scan is the standard, optimal way to test the subsequence relationship.
def is_subsequence(s, t):
i = 0
j = 0
while j < len(t) and i < len(s):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.