Word Break

Читайте s слева направо. Каким бы ни был первый фрагмент, это должно быть слово, с которого начинается s. Попробуйте каждое такое слово и для каждого задайте тот же вопрос об оставшихся буквах. Если какое-либо слово приводит к разбиению целиком, ответ — true. Если ни одно не приводит, ответ — false. Когда ничего не остаётся, значит, вы разделили все буквы, и это считается успехом.

Этот алгоритм пробует каждое возможное первое слово, затем каждое возможное второе слово и так далее, поэтому он не может пропустить подходящее разбиение, а каждый возвращаемый им результат true соответствует реальному разбиению.

Он работает медленно, потому что снова и снова проверяет одни и те же остатки. Возьмите 299 букв a, за которыми следует одна b, а также слова a, aa и так далее — вплоть до слова из десяти букв a. Любой способ разбить буквы a на блоки длиной не более десяти доходит до b и завершается неудачей, а таких способов больше, чем 10^89. Рекурсии приходится перебрать их все, прежде чем она сможет вернуть false.

Ответ для остатка зависит только от места, с которого он начинается, а start принимает только n + 1 значений. В примере с буквами a остаток, начинающийся с индекса 20, достигается после двух блоков по десять, после двадцати отдельных букв a и множеством других способов, и каждый раз ответ для него — false. Сохрани ответ для каждого начального места при первом вычислении, а затем считывай его.

Для ячейки мемоизации нужны три состояния: ещё не вычислено, true и false. Важны именно ответы false. Значение true немедленно завершает весь поиск, поэтому повторная работа обычной рекурсии происходит только в ветвях, которые завершаются неудачей.

Каждое начальное место вычисляется один раз и проверяет каждое слово, сравнивая до L букв, поэтому время работы составляет O(n × m × L): здесь не более 300 × 1000 × 20 = 6 × 10^6 проверок букв. Мемоизация и стек вызовов занимают O(n) места, а глубина вложенности вызовов не превышает 300.

Перевернём подход и будем работать с префиксами. Пусть canEnd[i] показывает, можно ли разбить первые i букв на слова. Для пустого префикса слова не нужны, поэтому canEnd[0] равно true. Первые end букв можно разбить тогда и только тогда, когда их последняя часть — буквы от start до end — является словом, а буквы перед ней можно разбить, то есть canEnd[start] равно true. Заполняйте таблицу слева направо, и каждое нужное значение canEnd[start] уже будет известно.

Вместо того чтобы сравнивать все m слов в каждой позиции, поместим слова в хеш-множество и будем проверять возможные последние части. Ни одно слово не длиннее L, поэтому совпасть могут только L частей, оканчивающихся на end. Для строки sunflowerseed значение canEnd становится равным true в позициях 0, 3 (sun), 7 (flow), 9 (flower) и 13 (seed после позиции 9), поэтому ответ — true. Позиция 7 никуда не ведёт, потому что ни одно слово не начинается с er, но таблице это не важно.

Есть n позиций, для каждой проверяется не более L частей, а создание части и её хеширование занимают до L шагов. Получаем O(n × L²), то есть не более 300 × 20 × 20 = 1.2 × 10^5 шагов по буквам, независимо от размера словаря. Для построения множества каждое слово читается один раз: O(m × L), поэтому общая сложность составляет O(m × L + n × L²). В множестве хранятся слова — O(m × L) букв, а в таблице — n + 1 флагов. Рекурсии нет.