Is Subsequence
(#392), Easy
Category: String, Two Pointer, Dynamic Programming
Problem Statement
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 formed by deleting some (or no) characters from the original string, without disturbing the relative order of the remaining characters.
Examples
Input: s = "abc", t = "ahbgdc"
Output: true
Explanation: "a", "b", and "c" appear in order in t.
Input: s = "axc", t = "ahbgdc"
Output: false
Explanation: "x" is not present in t, so s is not a subsequence.
Input: s = "ace", t = "abcde"
Output: true
Explanation: All characters of s appear in order in t.
Approach
Two Pointer Technique
- Initialize two pointers: `sIndex = 0` for string `s` and `tIndex = 0` for string `t`.
- Loop through string `t` using `tIndex`.
- At each step, if `s[sIndex] === t[tIndex]`, increment `sIndex` (we matched one character).
- Always increment `tIndex` regardless of match.
- After the loop ends, check if `sIndex === s.length`. If true, all characters of `s` were found in order inside `t`, so return true.
- Otherwise, return false.
var isSubsequence = function(s, t) {
let sIndex = 0;
let tIndex = 0;
while (tIndex < t.length) {
if (s[sIndex] === t[tIndex]) {
sIndex++;
}
tIndex++;
}
return sIndex === s.length;
};Complexity
Time: O(n), where n is the length of string t
Space: O(1), using just two pointers