145. Hidden Subsequence
A spy hides a short secret word s inside a longer message t by scattering the secret's letters through it. The letters of the secret stay in their original order, but other letters may appear between them. Nothing is rearranged, and each letter of the message can be used at most once.
Given two strings s and t, return true if s can be obtained from t by deleting zero or more characters of t without changing the order of the remaining ones, and false otherwise. In other words, decide whether s is a subsequence of t.
Example 1
- Input:
- s = "note", t = "xnyoztxe"
- Output:
- true
- Explanation:
Reading t from left to right we find n, then o, then t, then e, in that order, so the answer is true.
Example 2
- Input:
- s = "tone", t = "xnyoztxe"
- Output:
- false
- Explanation:
After matching t, o and n are both needed before e but the only n in the message comes before every t. The match gets stuck on the letter n, so the answer is false.
Constraints
1 ≤ s.length, t.length ≤ 105
s and t consist of lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n + m)
- Space
- O(1)