Код Senior Динамическое программирование обновлено
Разбиение на слова
Условие
Можно ли разбить строку на последовательность слов из словаря (слова можно использовать многократно)?
Примеры
wordBreak("leetcode", ["leet", "code"]) // true
wordBreak("applepenapple", ["apple", "pen"]) // true
wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]) // false
Как подойти
Классическая одномерная динамика по префиксам. Жадность «откусывать самое длинное слово» здесь неверна - контрпример как раз в тестах. Улучшение: ограничить внутренний цикл максимальной длиной слова словаря.
Подсказки: 2
- dp[i] - можно ли разбить префикс длины i.
- База dp[0] = true: пустая строка разбивается тривиально.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.