DP на строках (word break)

O(n^2)

Булев список ok[i] отмечает, делятся ли первые i символов чисто на слова из словаря. ok[0] изначально true, а ok[i] становится true, как только какое-то более раннее ok[j] равно true и кусок между j и i является настоящим словом.

Сигналы

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

Шаблон

function wordBreak(s, wordDict) {
    const words = new Set(wordDict);
    const ok = new Array(s.length + 1).fill(false);
    ok[0] = true;
    for (let i = 1; i <= s.length; i++) {
        for (let j = 0; j < i; j++) {
            if (ok[j] && words.has(s.slice(j, i))) {
                ok[i] = true;
                break;
            }
        }
    }
    return ok[s.length];
}

Похоже, но не то

DP над подпоследовательностями: DP над подпоследовательностями (LIS/LCS/расстояние редактирования) отслеживает самый длинный сохранённый отрезок по одной или двум последовательностям. Word break, наоборот, это просто булев массив по точкам разреза ОДНОЙ строки: ok[i] спрашивает лишь, делятся ли первые i букв на слова из словаря, без какого-либо самого длинного общего отрезка.

длина строки n до ~300..1000, проверка каждой более ранней точки разреза по словарю -> O(n^2) при O(1) проверках через Set/хеш.

Изучить этот паттерн