Word Break

The problem

You are given a string text and a list of words wordDict. Return true if text can be cut into pieces so that every piece is a word from the list. A word may be used any number of times.

Example 1

Input: text = "carpets", wordDict = ["carp", "car", "pets", "et"]

Output: true

“car” + “pets”. Starting with “carp” looks promising, but “carp” + “et” leaves an “s” that no word covers.

text

c0a1r2p3e4t5s6

Example 2

Input: text = "pencil", wordDict = ["pen", "cill"]

Output: false

After “pen”, the rest is “cil”, which is not a word.

Example 3

Input: text = "toptop", wordDict = ["top"]

Output: true

The same word can be used twice.

Constraints

• 1 ≤ text.length ≤ 300 (call it n)
• 1 ≤ wordDict.length ≤ 1000 (call it m)
• 1 ≤ wordDict[i].length ≤ 20 (call the longest k)
• Only lowercase English letters, and the words are all different.

Clarifying questions

Can a word be used more than once?

Yes, as often as needed.

Must every letter be used?

Yes. The pieces must cover the whole string with nothing left over.

Do we return the split?

No, only whether one exists. (Word Break II asks for all of them.)

Is the first matching word always safe to take?

No. In Example 1, "carp" matches but leads nowhere.

Spot the pattern

Look at the last word of a split. If the string ends with some word w, the question becomes: does the part before w split? That is the same question on a shorter prefix, and many choices lead to the same prefix. Answering each prefix once and reusing it is dynamic programming.

Solutions

Plain recursionO(2ⁿ × m × k)Table of prefixesO(n × m × k)

Show all

There is no middle tab. Adding a memo to the recursion reaches the same O(n × m × k) as the table. A trie of the words can speed up the matching, but the idea stays the same.

Plain recursion O(2ⁿ × m × k)

The idea

Let can(position) ask: can the letters from position to the end be split into words? If position is the end, yes. Otherwise, try every word. If the string has that word at position, take it and ask can(position + len(word)). If any choice works, return true. If none does, return false, and the caller tries its next word.

Why it is correct: every split begins with some word at position 0, and the search tries every word there, then every word after it, and so on. It only gives up on a choice once everything after it has failed.

Walkthrough

text

c0a1r2p3e4t5s6

words so far

-

call stack top →

empty

1. def can(position):
2. if position == len(text): return True
3. for word in words:
4. if text starts with word at position:
5. if can(position + len(word)): return True
6. return False
7. return can(0)

can(position) asks: can the letters from position to the end be split into words? Try each word that matches at position, and ask the same about the rest. Words: carp, car, pets, et.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private String text;
    private List<String> words;

    // Plain recursion: try every word that matches at the current position, and
    // solve the rest after it. A dead end is retried from scratch on every path that reaches it.
    public boolean wordBreak(String text, List<String> wordDict) {
        this.text = text;
        this.words = wordDict;
        return can(0);
    }

    private boolean can(int position) {
        // Reached the end: every letter is covered by a word.
        if (position == text.length()) return true;
        for (String word : words) {
            if (text.startsWith(word, position) && can(position + word.length())) return true;
        }
        return false;
    }
}

Big O

Time O(2ⁿ × m × k)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The work repeats through recursion. Each call loops over the m words, and checking one word compares up to k letters. So we count the calls, and the word checks inside each call.

   1. def can(position):
   2. if position == len(text): return True
   3. for word in words:
   4. if text starts with word at position:
   5. if can(position + len(word)): return True
   6. return False
   7. return can(0)

2. 2 Count the runs on Example 1

   The table has one column per call, in the order they ran. can(4) and can(6) checked all 4 words and found nothing that works. can(7) is the end, so it checks none.

   5 calls and 2 + 4 + 4 + 3 + 0 = 13 word checks.

   call	can(0)	can(4)	can(6)	can(3)	can(7)
   words checked	2	4	4	3	0

   total

   5 calls + 2 + 4 + 4 + 3 + 0 = 13 checks

3. 3 Write the count for any n

   Each call to can(position) comes from one way of cutting the first i letters into words. A string of i letters has i − 1 gaps, and each gap is a cut or not, so there are at most 2^(i − 1) ways. Over all i, that is fewer than 2ⁿ calls, and each does at most m checks of k letters:

   2ⁿ × m × k steps

   Check it with Example 1: 2⁷ = 128 calls at most. The real run made 5, because few words match. A string like “aaaaaaaaab” with the words “a”, “aa” and “aaa” really does try a huge number of cuts before failing.

4. 4 Keep only the part that grows fastest

   Nothing to drop: it is exponential in n. With n = 300, far too slow.

   So the time is O(2ⁿ × m × k).

5. S Space: count the extra memory the same way

   The call stack holds one chain of calls, at most n + 1 deep. So the space is O(n).

   call stack (up to n deep)

Table of prefixes O(n × m × k)

The idea

The recursion asks about the same positions many times. There are only n + 1 of them, so decide each once, in a table.

Let splittable[i] be true when the first i letters split into words. splittable[0] is true: no letters, no words. For i from 1 to n, look for a word that could be the last word of the prefix: the prefix ends with word, and splittable[i - len(word)] is true. If one exists, splittable[i] is true. The answer is splittable[n].

Why it is correct: a prefix splits exactly when it ends with some word and the part before that word splits. Shorter prefixes are filled in first, so their answers are final when they are read.

Walkthrough

text

c0a1r2p3e4t5s6

splittable

T01234567

1. splittable = [True] + [False] * len(text)
2. for i in 1 .. len(text):
3. for word in words:
4. if splittable[i - len(word)] and text[i - len(word):i] == word:
5. splittable[i] = True; break
6. return splittable[len(text)]

splittable[i] says whether the first i letters split into words. splittable[0] is true: zero letters need zero words. Fill the rest from left to right.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Table, bottom up: splittable[i] says whether the first i letters split into words.
    // Each prefix is decided once, from shorter prefixes. O(n × m × k) time, O(n) space.
    public boolean wordBreak(String text, List<String> wordDict) {
        boolean[] splittable = new boolean[text.length() + 1];
        // The empty prefix needs no words.
        splittable[0] = true;
        for (int i = 1; i <= text.length(); i++) {
            for (String word : wordDict) {
                // w can be the last word if the letters before it already split.
                if (word.length() <= i && splittable[i - word.length()]
                    && text.startsWith(word, i - word.length())) {
                    splittable[i] = true;
                    break;
                }
            }
        }
        return splittable[text.length()];
    }
}

Big O

Time O(n × m × k)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The inner loop checks one word against the end of the prefix. That compares up to k letters, so each word check is up to k steps.

   1. splittable = [True] + [False] * len(text)
   2. for i in 1 .. len(text):
   3. for word in words:
   4. if splittable[i - len(word)] and text[i - len(word):i] == word:
   5. splittable[i] = True; break
   6. return splittable[len(text)]

2. 2 Count the runs on Example 1

   The table has one column per prefix length. A prefix stops checking at the first word that works: “carp” at length 4 needed only 1 check.

   4 + 4 + 2 + 1 + 4 + 4 + 3 = 22 word checks.

   i	1	2	3	4	5	6	7
   words checked	4	4	2	1	4	4	3

   total

   4 + 4 + 2 + 1 + 4 + 4 + 3 = 22 checks

3. 3 Write the count for any n

   The outer loop runs n times, the inner loop at most m times, and each check reads at most k letters:

   n × m × k steps

   Check it with Example 1: 7 × 4 = 28 word checks at most. The real run made 22.

4. 4 Keep only the part that grows fastest

   Nothing to drop. It is O(n × m × k): at most 300 × 1000 × 20 = 6 million steps.

   So the time is O(n × m × k).

5. S Space: count the extra memory the same way

   The table has n + 1 slots. So the space is O(n).

   splittable table (n + 1)

Common mistake

Taking the first word that matches

Grabbing the first match and moving on is greedy. In Example 1 it takes “carp”, then “et”, and is stuck on “s”. The table avoids this because it remembers every prefix that splits, not just one.

Tested at the limits

2,000 random inputs: words of 1 to 3 letters made of a and b, and a text of up to 12 letters mostly built from those words, sometimes with one letter changed. The plain recursion and the table of prefixes gave the same answer every time.

Largest inputs	Result
300 letters and 1,000 words of up to 20 letters (the most allowed): 299 a then a b, with the words of only a at the end of the list. Table of prefixes.	0.02 s, and about 0.002 MB of extra memory: one list of 301 flags, O(n).
21 a then a b, with words of 1 to 5 a. Plain recursion.	0.3 s. It tries every way to split the a again and again before it fails. At 300 letters it would never finish.