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

DP на строках (word break): как это работает?

Состояние i значит, что первые i символов можно разрезать. Нулевое состояние истинно по определению.

Для каждой позиции i смотрите назад на все более ранние позиции j. Кусок между ними это кандидат в слово.

Разрез работает, если состояние j истинно и кусок это слово. Тогда истинно и состояние i.

Одного подходящего j достаточно. Прерывайте внутренний цикл сразу после находки.

Ответ лежит в последнем состоянии. Дальше позиции n ничего нет.

Каждая позиция решается ровно один раз. Именно это превращает экспоненту в таблицу.

1. dp[0] = истинаРежем leetcode словами leet и code.
2. dp[1] по dp[3] = ложьКуски l, le и lee словами не являются.
3. dp[4] = истинаleet это слово, а dp[0] истинно.
4. dp[5] по dp[7] = ложьНи одно слово не кончается в этих позициях.
5. dp[8] = истинаcode идёт после dp[4]. Вся строка режется.

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 на строках (word break): разбор примера

Наименьшее число разрезов на палиндромы

Разрежьте строку на куски, каждый из которых палиндром. Верните наименьшее число разрезов.

Один символ уже считается палиндромом.

Сначала отметьте все пары позиций, между которыми стоит палиндром.

Потом состояние i это наименьшее число разрезов для первых i символов. Палиндромный хвост стоит одного разреза.

function minCut(s) {
    const n = s.length;
    const isPal = Array.from({ length: n }, () => new Array(n).fill(false));

    for (let end = 0; end < n; end++) {
        for (let start = end; start >= 0; start--) {
            // the inside is already decided, because end - start only shrinks
            if (s[start] === s[end] && (end - start < 2 || isPal[start + 1][end - 1])) {
                isPal[start][end] = true;
            }
        }
    }

    const cuts = new Array(n + 1).fill(0);
    for (let i = 0; i <= n; i++) cuts[i] = i - 1; // cuts[0] is -1, so a whole palindrome costs 0

    for (let end = 0; end < n; end++) {
        for (let start = 0; start <= end; start++) {
            if (isPal[start][end]) {
                cuts[end + 1] = Math.min(cuts[end + 1], cuts[start] + 1);
            }
        }
    }

    return cuts[n];
}

DP на строках (word break): когда применять?

Эти формулировки в условии ведут сюда:

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

DP на строках (word break): с чем путают?

• DP над подпоследовательностями (LIS / LCS / расстояние редактирования) (DP on subsequences (LIS / LCS / edit distance)): Там выравниваются две разные последовательности. Здесь режется одна строка.
• Trie (префиксное дерево) (Trie (prefix tree)): Trie ускоряет поиск по словарю. Логика разрезания над ним не меняется.
• Бэктрекинг (Backtracking): Бэктрекинг перечисляет все верные разрезы. Таблица отвечает лишь, есть ли хоть один.
• Хеш-множество / словарь (Hash set / map): Словарь слов обычно и есть множество. Таблица нужна, чтобы не проверять суффикс заново.

DP на строках (word break): частые ошибки

• Пересобирают подстроку на каждом шаге

  Вырезание внутри цикла каждый раз копирует символы. Сравнивайте позиции или идите по trie.

• Идут по палиндромам не в ту сторону

  Внутренность обязана решаться раньше внешней. Растите по длине или ведите начало назад.

• Забывают пустой префикс

  Нулевое состояние и позволяет первому слову начать разрез. Без него истины не будет никогда.

• Перечисляют все разрезы, когда хватит одного

  Задача спрашивает только да или нет. Перечисление разрезов экспоненциально.

DP на строках (word break): задачи с собеседований

• Разбиение строки на слова: Можно ли вообще разрезать строку.
• Разбиение строки на слова II: Нужны все верные разрезы, поэтому возвращается бэктрекинг.
• Разбиение на палиндромы II: Нужно число разрезов, а не сами части.
• Наибольшая палиндромная подстрока: Та же таблица палиндромов, прочитанная иначе.
• Составные слова: Каждое слово режется при помощи всех остальных.
• Лишние символы в строке: Считается стоимость оставшихся букв.
• Число способов расшифровки: Одна цифра или две, по фиксированному алфавиту.

DP на строках (word break): сложность по времени и памяти

O(n^2)

n символов при словах до m дают O(nm). Множество или trie держат поиск около O(1).