Задача с собеседования в Яндекс

Реализовать функцию fuzzy pussy search как в редакторе sublime text 3.

Для незнакомых с редактором - по факту требуется проверить, является ли первая строка подпоследовательностью второй

fuzzysearch('car', 'cartwheel') -> true

наш чат алгоритмистов

Решение:
Один проход по символам строки

def fuzzysearch(needle, haystack):
if not needle:
return True
if not haystack:
return False

i = 0 # индекс в needle
for char in haystack:
if char == needle[i]:
i += 1
if i == len(needle):
return True
return False

Асимптотика O(N)

@algoses