В этой задаче LeetCode нам дается строка и последовательность слов, и нас просят найти все точки в строке, где затем можно найти все слова в любом порядке, без перерыва.
Другими словами, учитывая строку redgreenblue и слова ['red', 'green'] , вы вернете [0] , так как вы можете найти все слова непрерывными в этой точке. Если бы вместо этого была строка redgreengreenred , вы бы вернули [0, 8], поскольку комбинация предоставленных слов также может быть найдена в конце строки.
Решение №1: рекурсия
Основная предпосылка для этого решения заключается в том, что мы перебираем исходную строку и для каждой итерации проверяем, можно ли найти все целевые слова, начиная с этой точки в строке. Чтобы достичь более сложной второй половины этого, мы будем использовать рекурсию.
Рекурсивная функция doesStringContainAllWords принимает строку и массив слов и проверяет, не найдено ли какое-либо из этих слов в начале строки. Если это так, мы снова вызываем функцию, предоставляя ту же строку, но перемещаясь на длину найденного слова, и тот же массив слов, за вычетом найденного. Как только все слова будут найдены, мы подтверждаем, что исходная строка действительно содержала все целевые слова.
Чтобы ускорить работу с этим общим подходом, мы также сначала вычисляем общую длину всех искомых слов. Это позволяет нам выйти раньше, когда мы пройдем достаточно далеко по строке, чтобы знать, что ответ больше не может быть найден.
