#392
Is Subsequence
Easy Same direction
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether s can be obtained from t by deleting some characters without changing the order of the rest.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: can you find s's letters inside t in the same order?
Why this works: walk t once; whenever its letter matches the next needed letter of s, move forward in s.
Example: s = "abc", t = "ahbgdc"
a ✓, h, b ✓, g, d, c ✓ → all found → true✦Hints open one at a time
Walk through t once with a pointer into s.
Advance the s pointer only when characters match.
↗Approach
Greedy matching: for each character of t, if it equals the next needed character of s, move forward in s. s is a subsequence if you reach its end.
</>Solution (Java)
class Solution {
public boolean isSubsequence(String s, String t) {
int i = 0;
for (int j = 0; j < t.length() && i < s.length(); j++) {
if (s.charAt(i) == t.charAt(j)) i++; // matched one more char of s
}
return i == s.length();
}
}!Common mistake
Using indexOf for each character from the start of t each time, which ignores order.
Complexity
- Time: O(|t|).
- Space: O(1).
