Нечёткий поиск подпоследовательности (Fuzzy Search)

Условие:

Даны две строки: needle и haystack. Нужно определить, можно ли получить needle, удалив из haystack некоторые символы (ноль или более), не меняя порядок оставшихся символов. Другими словами, все символы needle должны встречаться в haystack в том же порядке, но необязательно подряд.

Функция должна быть реализована за один проход по символам обеих строк, без использования регулярных выражений.

Входные данные:

• needle — строка, которую нужно найти

• haystack — строка, в которой производится поиск

Выходные данные:

• true/True, если needle является подпоследовательностью haystack, иначе false/False

Ограничения:

• 0 <= длина needle <= 10^4

• 0 <= длина haystack <= 10^5

• Строки состоят из печатных ASCII-символов

Пример:

Вход: needle = "car", haystack = "cartwheel"
Выход: true

Вход: needle = "cwhl", haystack = "cartwheel"
Выход: true

Вход: needle = "cartwheeel", haystack = "cartwheel"
Выход: false

Вход: needle = "lw", haystack = "cartwheel"
Выход: false