Word Break

Средняя№139одномерный массив

Даны строка и список слов. Можно ли разрезать строку на куски так, чтобы каждый кусок был словом из списка? Слово можно брать много раз. Наш пример: «seashell» и слова sea, seas, hell — да, seas + hell.

139 Word BreakРазбор · 1×

Пример: «seashell», слова sea, seas, hell. Смотрите на разбиение после sea: оно настоящее, но ведёт в тупик.

wordsseaseashellsokseashell012345678
i: эта позицияtrue: здесь кончается разбиениеслово подходитслово не подходитответ и его разбиение

ok[i]: можно ли первые i букв seashell разбить на слова? 9 клеток, пока все false

01/28
сначала · назад · пуск · шаг
Скорость
1function wordBreak(s, words):
2 ok = array of size len(s) + 1, all false
3 ok[0] = true // the empty start
4 for i from 0 to len(s) - 1:
5 if not ok[i]:
6 continue // no split ends at i
7 for each w in words:
8 if s from i starts with w:
9 ok[i + len(w)] = true
10 return ok[len(s)]
состояние
ok
[false, false, false, false, false, false, false, false, false]
i
–
w
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Разбиение первых j букв кончается каким-то словом w, а перед ним разбиваются первые j − len(w) букв. Значит, ok[j] = true ровно тогда, когда за одно слово до него стоит клетка true, и если класть каждое слово от каждой клетки true, найдутся все такие.
  2. Одной клетки true мало: после sea остаток shell не начинается ни с одного слова, и эта ветка просто обрывается. Слово seas ведёт в ok[4], а оттуда hell доходит до конца.
  3. Перебор режет строку всеми способами и снова и снова пробует продолжения с одного и того же индекса. Таблица отвечает на каждый индекс один раз.

Сложность

Время O(n × слова × длина слова): из каждой из n позиций каждое слово сравнивается по буквам. Память O(n) на таблицу.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.