Где применяется
1. Задача
У тебя одна длинная строка букв без пробелов, например "leetcode", и словарь известных слов, например ["leet", "code"]. Вопрос простой: можно ли разрезать строку на целые слова так, чтобы каждое из них было в словаре? Одно слово можно брать сколько угодно раз. Пустая строка тоже считается разрезанной: в ней ноль слов.
"leetcode" режется на "leet" и "code", поэтому ответ да. "applepenapple" режется на "apple", "pen", "apple", слово "apple" взято дважды, и ответ снова да.
Теперь "catsandog" со словарём ["cats", "dog", "sand", "and", "cat"]. Кажется, что должно получиться: "cats", потом "and", потом остаётся "og", а это не слово. Пробуешь "cat", "sand", и снова остаётся "og". При любом разрезе остаётся хвост, поэтому ответ нет. Брать первое подходящее слово нельзя. Нужно знать, режется ли на слова остаток строки.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитwordBreak("catsdog", ["cat", "cats", "dog"])Можно ли разрезать "catsdog" на слова из словаря? ok[0] истинно: пустому префиксу слова не нужны.
Столбики: сколько проверок по словарю начиналось с каждой позиции строки.
Одна операция: одна проверка по словарю. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(2ⁿ)O(n²)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- можно ли разбить строку на слова из словаря
- сегментировать строку по списку слов
- булево значение достижимости в каждой точке разреза
- слитный текст нужно разделить на границы слов
Похоже, но не то
- DP над подпоследовательностями (LIS / LCS / расстояние редактирования) (DP on subsequences (LIS / LCS / edit distance))
Там выравниваются две разные последовательности. Здесь режется одна строка.
- Trie (префиксное дерево) (Trie (prefix tree))
Trie ускоряет поиск по словарю. Логика разрезания над ним не меняется.
- Бэктрекинг (Backtracking)
Бэктрекинг перечисляет все верные разрезы. Таблица отвечает лишь, есть ли хоть один.
- Хеш-множество / словарь (Hash set / map)
Словарь слов обычно и есть множество. Таблица нужна, чтобы не проверять суффикс заново.
n символов при словах до m дают O(nm). Множество или trie держат поиск около O(1).
На LeetCode
Задачи, где строку режут на куски из словаря или на допустимые коды и спрашивают, получится ли, сколькими способами или какой разрез дешевле. ok[i] говорит, что первые i букв режутся без остатка, и он берётся из любого раннего разреза j, где ok[j] true, а кусок от j до i допустим.
Задача урока. Положи слова в Set, чтобы каждая проверка куска стоила в среднем O(1).
Куски здесь это одна цифра от 1 до 9 или две цифры от 10 до 26, а таблица считает способы там, где урок отвечает да или нет.
Таблица хранит наименьшее число лишних букв для каждого префикса. Это значение для предыдущего префикса плюс один или значение более раннего префикса, если промежуток закрывает слово из словаря.
Здесь нужно перечислить все разрезы. Перебирай их бэктрекингом и храни в мемо готовые предложения для каждой стартовой позиции.