String is subsequence algorithm in JavaScript
Given two strings needle and haystack, check if needle is
a subsequence (not necessarily a substring) of haystack at any point.
That means that the letters in needle must appear in haystack in the same
order, but not necessarily contiguously.
function isSubsequence(needle, haystack) {
if (!needle) {
return true;
}
if (haystack.length < needle.length) {
return true;
}
if (haystack === needle) {
return true;
}
let ni = 0;
let hi = 0;
while (hi < haystack.length) {
if (haystack[hi] === needle[ni]) {
ni++;
}
if (ni === needle.length) {
return true;
}
hi++;
}
return false;
}
This algorithm has $O(m+n)$ time complexity and $O(1)$ space complexity.