Word Break

The problem

You are given a string s and a list of words, words. Return true if s can be cut into pieces so that every piece is one of the words, and false if it cannot. The pieces must use up all of s with nothing left over. A word may be used for more than one piece, and not every word has to be used. An empty s needs no pieces, so its answer is true even when words is empty.

What to write

function solve(s: string, words: string[]): boolean

Input
s = "applepenapple"
words = ["apple","pen"]

Output
true

Input
s = "catsandog"
words = ["cats","dog","sand","and","cat"]

Output
false

Constraints

0–200 lowercase characters; at most 100 nonempty dictionary words of length ≤ 30.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   A word that matches at the start is not always the right first piece: with the words cats, cat and sand, the string catsand has to begin with cat, not cats. So one choice per place is not enough. But s has at most 200 letters, so there are few places where a piece can end.

2. Hint 2: Ask a smaller question

   Take catsandog with the words cats, dog, sand, and, cat. The string ends with dog. What would have to be true of the letters before it, catsan, for that to help? How would you find that out?

3. Hint 3: Name the pattern

   Call the first few letters of s a prefix. A prefix can be split if some word ends it and the shorter prefix before that word can be split too. One yes or no answer per prefix, each worked out once from shorter ones, is one-dimensional dynamic programming. The signal: a sequence to cut into allowed pieces. Read the lesson on one-dimensional dynamic programming.

4. Hint 4: State the invariant

   The table has one mark for every prefix length from 0 to the length of s. The mark for length i is true exactly when the first i letters of s can be cut into words with nothing left over. Length 0, the empty prefix, is true.

5. Hint 5: Sketch the pseudocode

   mark[0] = true, all other marks false. For i from 1 to the length of s: for each word w no longer than i: if mark[i - length of w] is true and the first i letters end with w, set mark[i] = true and move on to the next i. Return mark[length of s].

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Mark the empty prefix reachable. A longer prefix is reachable when removing a matching last dictionary word leaves a reachable prefix.

The slow way

Try every word that matches the start of s, and for each one do the same with the rest of the string. It is correct, but the same rest is tried again every time a different split leads to it. For 25 a's followed by b, with the words a, aa and aaa, that takes 5,600,910 calls.

The insight

Whether the rest of the string can be split does not depend on how you got there. So each place in s needs one answer, not one per route. Turned around: the first i letters can be split if some word ends them and the letters before that word can be split too.

Step by step

1. Make a table of marks, one per prefix length from 0 up, all false. A prefix is the first so many letters of the string. Its mark will say whether those letters can be cut into words with nothing left over. Nothing is known yet, so every mark starts false.
2. Mark length 0 true: the empty prefix needs no words. With no letters there is nothing left to cut, so the empty prefix counts as split. A word at the very start of the string has this prefix before it.
3. Decide each longer prefix in turn, shortest first. A mark is worked out from the marks of shorter prefixes, so those have to be final first.
4. Try each word as the last word of this prefix. If the prefix can be split, the split ends with some word. You do not know which, so every word gets a turn.
5. It fits if the prefix ends with it and the part before is marked true. Ending with the word is not enough: the letters before the word must be cut into words as well, and their mark already says whether they can. A word longer than the prefix cannot end it.
6. One word that fits is enough: mark this prefix true and stop trying. The question is whether a split exists, not how many there are, so the other words cannot change this mark.
7. Return the mark of the whole string. The longest prefix is the whole string, so its mark is the answer. For an empty string that is the mark set at the start, true.

The same numbered steps are the comments in each solution.

function solve(s, words) {
  // 1. Make a table of marks, one per prefix length from 0 up, all false
  const dp = Array(s.length + 1).fill(false);
  // 2. Mark length 0 true: the empty prefix needs no words
  dp[0] = true;
  // 3. Decide each longer prefix in turn, shortest first
  for (let i = 1; i <= s.length; i++) {
    // 4. Try each word as the last word of this prefix
    for (const w of words) {
      // 5. It fits if the prefix ends with it and the part before is marked true
      if (
        w.length <= i &&
        dp[i - w.length] &&
        s.slice(i - w.length, i) === w
      ) {
        // 6. One word that fits is enough: mark this prefix true and stop trying
        dp[i] = true;
        break;
      }
    }
  }
  // 7. Return the mark of the whole string
  return dp[s.length];
}

function solve(s: string, words: string[]): boolean {
  // 1. Make a table of marks, one per prefix length from 0 up, all false
  const dp = Array(s.length + 1).fill(false);
  // 2. Mark length 0 true: the empty prefix needs no words
  dp[0] = true;
  // 3. Decide each longer prefix in turn, shortest first
  for (let i = 1; i <= s.length; i++) {
    // 4. Try each word as the last word of this prefix
    for (const w of words) {
      // 5. It fits if the prefix ends with it and the part before is marked true
      if (
        w.length <= i &&
        dp[i - w.length] &&
        s.slice(i - w.length, i) === w
      ) {
        // 6. One word that fits is enough: mark this prefix true and stop trying
        dp[i] = true;
        break;
      }
    }
  }
  // 7. Return the mark of the whole string
  return dp[s.length];
}

def solve(s, words):
    # 1. Make a table of marks, one per prefix length from 0 up, all false
    dp = [False] * (len(s) + 1)
    # 2. Mark length 0 true: the empty prefix needs no words
    dp[0] = True
    # 3. Decide each longer prefix in turn, shortest first
    for i in range(1, len(s) + 1):
        # 4. Try each word as the last word of this prefix
        for word in words:
            # 5. It fits if the prefix ends with it and the part before is marked true
            start = i - len(word)
            if start >= 0 and dp[start] and s[start:i] == word:
                # 6. One word that fits is enough: mark this prefix true and stop trying
                dp[i] = True
                break
    # 7. Return the mark of the whole string
    return dp[len(s)]

Example 2, traced

Input
s = "catsandog"
words = ["cats","dog","sand","and","cat"]

Output
false

Why it works

The mark for length i is true exactly when the first i letters can be cut into words with nothing left over. Such a cut ends with some word, and the letters before that word form a shorter prefix that can be cut as well. Shorter prefixes are decided first, so every mark is read only after it is final.

Time and space

Time O(n × word count × max word length), extra space O(n). One mark per prefix length is the O(n) space for n letters. Each length tries every word, and comparing a word with the end of the prefix reads up to all its letters. So the time is n times the number of words times the longest word.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Cutting off a word that matches and never going back. With the words cats, cat and sand, taking cats from catsand leaves three letters that are no word, so the answer is false. Yet cat followed by sand works.
• Leaving the mark of length 0 false. Then no word at the start of the string ever fits, no mark becomes true, and every answer is false, even for an empty string.
• Marking a prefix true because it ends with a word, without reading the mark of the part before the word. Then catsandog counts as split because it ends with dog, although catsan cannot be split.

Pattern

One-dimensional dynamic programming. Builds on Decode Ways and Coin Change.

Keep going