Word Break

Medium#1391d array

You get a string and a list of words. Can the string be cut into pieces so that every piece is a word from the list? A word may be used many times. Our example: "seashell" with the words sea, seas, hell — yes, seas + hell.

139 Word BreakWalkthrough · 1×

Example: "seashell", words sea, seas, hell. Watch the split after sea: it is a real split, and still a dead end.

wordsseaseashellsokseashell012345678
i: this positiontrue: a split ends herethe word fitsthe word does not fitanswer and its split

ok[i]: can the first i letters of seashell be split into words? 9 cells, all false for now

01/28
restart · back · play · step
Speed
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)]
state
ok
[false, false, false, false, false, false, false, false, false]
i
–
w
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A split of the first j letters ends with some word w, and before it the first j − len(w) letters split too. So ok[j] is true exactly when a true cell lies one word before it, and laying every word from every true cell finds them all.
  2. A true cell is not enough on its own: after sea the rest shell starts with no word, and that branch just stops. The word seas leads to ok[4], and from there hell reaches the end.
  3. Brute force cuts the string in every possible way, and the ways to continue from the same index are tried again and again. The table answers each index once.

Complexity

Time O(n × words × length of a word): from each of the n positions every word is compared letter by letter. Memory O(n) for the table.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.