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];
}

function wordBreak(s: string, wordDict: string[]): boolean {
    const words = new Set(wordDict);
    const ok = new Array<boolean>(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];
}

def word_break(s, word_dict):
    words = set(word_dict)
    ok = [False] * (len(s) + 1)
    ok[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if ok[j] and s[j:i] in words:
                ok[i] = True
                break
    return ok[len(s)]

function wordBreak(string $s, array $wordDict): bool {
    $words = array_flip($wordDict);
    $n = strlen($s);
    $ok = array_fill(0, $n + 1, false);
    $ok[0] = true;
    for ($i = 1; $i <= $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($ok[$j] && isset($words[substr($s, $j, $i - $j)])) {
                $ok[$i] = true;
                break;
            }
        }
    }
    return $ok[$n];
}

    public static boolean wordBreak(String s, String[] wordDict) {
        Set<String> words = new HashSet<>(Arrays.asList(wordDict));
        boolean[] ok = new boolean[s.length() + 1];
        ok[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (ok[j] && words.contains(s.substring(j, i))) {
                    ok[i] = true;
                    break;
                }
            }
        }
        return ok[s.length()];
    }

    public static bool WordBreak(string s, string[] wordDict) {
        var words = new HashSet<string>(wordDict);
        var ok = new bool[s.Length + 1];
        ok[0] = true;
        for (int i = 1; i <= s.Length; i++) {
            for (int j = 0; j < i; j++) {
                if (ok[j] && words.Contains(s.Substring(j, i - j))) {
                    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)» нужен, когда в условии есть слова «можно ли разбить строку на слова из словаря», «сегментировать строку по списку слов» или «булево значение достижимости в каждой точке разреза». Решение на нём обычно укладывается в O(n^2).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «DP на строках (word break)» чаще всего путают с этими паттернами: DP над подпоследовательностями (LIS / LCS / расстояние редактирования), Trie (префиксное дерево), Бэктрекинг и Хеш-множество / словарь.

• 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): задачи с собеседований

Паттерн «DP на строках (word break)» решает такие задачи с собеседований: Разбиение строки на слова, Разбиение строки на слова II, Разбиение на палиндромы II, Наибольшая палиндромная подстрока, Составные слова, Лишние символы в строке и Число способов расшифровки.

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

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

У паттерна «DP на строках (word break)» целевая сложность O(n2).

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