MiddleCodeOccasionalNot answered yet
Implement fuzzysearch: is needle a subsequence of haystack?
Implement fuzzysearch(needle, haystack) as in a code editor's fuzzy match: return true if needle is a subsequence of haystack (its characters appear in order, not necessarily contiguous). E.g. fuzzysearch("cwhl", "cartwheel") is true, fuzzysearch("lw", "cartwheel") is false.
Requirements:
- One pass, no recursion. O(|haystack|).
bool fuzzysearch(const std::string& needle, const std::string& haystack) {
// your code here
}Write the implementation.
Use two pointers. Walk haystack; whenever the current haystack char equals the current needle char, advance the needle pointer. The needle is a subsequence iff its pointer reaches the end. One linear pass over the haystack, O(|haystack|), constant extra space.
- ✗Confusing subsequence (order preserved, gaps allowed) with substring (contiguous)
- ✗Only checking character presence and ignoring relative order
- ✗Advancing the needle pointer on every haystack char instead of only on a match
- →What clarifying questions matter here (empty needle, case sensitivity)?
- →Why does the single-pass greedy match never miss a valid subsequence?
Contents
Task
Check whether needle is a subsequence of haystack, in one pass without recursion.
Solution
bool fuzzysearch(const std::string& needle, const std::string& haystack) {
size_t n = 0;
for (char c : haystack) {
if (n < needle.size() && c == needle[n]) ++n;
if (n == needle.size()) return true;
}
return n == needle.size();
}Key points
- The needle pointer advances only on a match; the haystack pointer always advances.
- Subsequence, not substring: gaps allowed, order required.
- One pass, O(|haystack|), constant memory.
Contents
