Is Subsequence
LeetCode 392 • Easy • Two Pointers
Return true if s is a subsequence of t. Two pointers: match s[i] in t, advance i on match, always advance j.
TimeO(n)single pass over t
SpaceO(1)two pointers
i: —
j: —
Result: —
Ready
Press Play. Two pointers: i on s, j on t. If s[i]==t[j], advance i; always advance j. Return i==len(s).
TimeO(n)single pass
SpaceO(n)call stack
Recursive: helper(i, j) — base: if i==len(s) return True; if j==len(t) return False; if s[i]==t[j] return helper(i+1,j+1); return helper(i,j+1).
3
Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.
PATTERN ▸ Two pointers (i on match, j always) O(n) · O(1)
① BASE CASE
if not s: return True
② INIT POINTERS
i, j = 0, 0
③ LOOP
while i < len(s) and j < len(t):
④ MATCH & ADVANCE
if s[i] == t[j]: i += 1
j += 1
⑤ RETURN
return i == len(s)
▼ your implementation ▼
Verify your solution: