Problem 392 - Is Subsequence
Given a string s
and a string t
, check if s
is a subsequence of t
.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace"
is a subsequence of "abcde"
while "aec"
is not).
Examples
Input: s = "abc", t = "ahbgdc"
Output: true
Input: s = "axc", t = "ahbgdc"
Output: false
Conceptual Overview
Since we want to check if s
is a subsequence of t
we will want to check every character of s
against t
and if a character at s
matches a character in t
(in order) then we can move onto the next character in s
and do the check all over again.
Looking at the example above let's run through a couple of iterations. In ECMAScript 5 we can treat the string as an array-like object, where individual characters correspond to a numerical index.
1) At s[0] = a; t[0] = a; does s[0] === t[0]? Yes, move to the next character in s
and t
2) At s[1] = b; t[1] = h; does s[1] === t[0]? No, move to the next character in t
3) At s[1] = b; t[2] = b; does s[1] === t[2]? Yes, move to the next character in s
and t
...
6) At s[2] = c; t[5] = c; does s[3] === t[5]? Yes, and since we went through the length of s
we found s
to be a subsequence of t
Code
While-loop variation
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
const isSubsequence = (s, t) => {
if (s.length === 0) return true
let sPointer = 0
let tPointer = 0
while (sPointer < s.length && tPointer < t.length) {
if(s[sPointer] === t[tPointer]) sPointer++
tPointer++
}
return sPointer === s.length
};
For-loop variation
const isSubsequence = (s, t) => {
if (s.length === 0) return true
let sPointer = 0
for (let i = 0; i < t.length; i++) {
if (s[sPointer] === t[i]) sPointer++
}
return sPointer === s.length
}
In both code solutions, we need to keep track of our position in each string so we use pointers to help with that.
Time & Space Complexity
Time: O(n) - where n is the length of the array
Space: O(1)
Both variations have the same time and space complexity
Top comments (0)