Word Break

Q: What is the time complexity of Word Break?

The bottom-up table with a hash set runs in O(m × L + n × L²) time, where n is the length of s , m the number of words and L the longest word. Building the set reads every word once, and each of the n positions looks up at most L pieces of up to L letters. If you compare every word at every position instead, it is O(n × m × L) . Plain recursion without a memo is exponential.

Q: Is Word Break a dynamic programming or a graph problem?

Both views work. As dynamic programming, canEnd[i] answers whether the first i letters can be cut, built from smaller prefixes. As a graph, every index is a node with an edge from i to j when the letters from i to j form a word, and you ask whether node n is reachable from node 0. A breadth-first search with a visited set does the same work as the table.

MediumDynamic programming Hashing

+10

You get a string s and a list of words wordDict. Return true if you can cut s into pieces so that every piece is a word from wordDict, and false otherwise.

The pieces keep their order and together use every letter of s exactly once. A word may be used any number of times, and you do not have to use every word.

Function

wordBreak(s: string, wordDict: string-array) → boolean

sstring: the string to cut into words
wordDictstring-array: the words you may use, each as often as you like
Returnsboolean: true if s can be cut into dictionary words, false otherwise

Constraints

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s and every word hold only lowercase English letters.
The words in wordDict are all different.

Examples

Input: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
Output: true
Explanation: Cut it as sun, flower, seed. Taking flow after sun leads nowhere, since no word starts with the er that is left, so the first word that fits is not always the right one.

Input: s = "bananaban"wordDict = ["ban", "ana"]
Output: true
Explanation: ban + ana + ban covers the string and uses ban twice, which is allowed.

Input: s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
Output: false
Explanation: The string starts with pine + apple or with pineapple, and both leave tart. The only word that fits there is tar, which leaves a lone t, so no cut works.

+21 hidden tests on Submit

Follow-up

Return the fewest words a valid cut can use, or -1 if s cannot be cut. What changes in the table, and does the running time change?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Cutting greedily fails in both directions: taking the shortest word first sends sunflowerseed into sun + flow, and taking the longest first cuts carpetal as carpet and strands al. So you have to try the choices, and a string can be cut in exponentially many ways. What cracks it is that whether the rest of the string can be cut depends only on where the rest starts, so there are only n + 1 different questions. Below, n is the length of s, m the number of words and L the length of the longest word.

Try every word at every position

Correct, but does not finish on the largest tests

Intuition

Read s from the left. Whatever the first piece is, it must be a word that s starts with. Try each such word, and for each one ask the same question about the letters that remain. If any word leads to a full cut, the answer is true. If none does, it is false. When nothing remains, you have cut every letter, so that counts as success.

This tries every possible first word, then every possible second word, and so on, so it cannot miss a valid cut, and every true it returns comes with a real cut.

It is slow because it checks the same remainders over and over. Take 299 copies of a followed by one b, with the words a, aa and so on up to ten as. Every way to cut the a's into blocks of at most ten reaches the b and fails there, and there are more than 10^89 such ways. The recursion has to try them all before it can answer false.

Algorithm

Write a helper canSplit(start) that says whether the letters from index start to the end can be cut into words.
If start equals the length of s, return true.
For each word, check whether s contains it starting at index start.
If it does and canSplit(start + length of the word) is true, return true.
If no word works, return false. The answer is canSplit(0).

def wordBreak(s, wordDict):
    def can_split(start):
        # Can s[start:] be cut into dictionary words?
        if start == len(s):
            return True  # nothing left to cut
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                return True
        return False

    return can_split(0)

Recursion with a memo

Intuition

The answer for a remainder depends only on where it starts, and start takes only n + 1 values. In the a's example, the remainder that starts at index 20 is reached after two blocks of ten, after twenty single as and in a huge number of other ways, and its answer is false every time. Store the answer for each start the first time you work it out, and read it back afterwards.

A memo slot needs three states: not worked out yet, true and false. The false answers are the ones that matter. A true ends the whole search at once, so the work the plain recursion repeats is all in branches that fail.

Each start is worked out once and tries every word, comparing up to L letters, so the time is O(n × m × L): at most 300 × 1000 × 20 = 6 × 10^6 letter checks here. The memo and the call stack take O(n) space, and the calls nest at most 300 deep.

Algorithm

Make a memo with one slot per index, each marked as not worked out.
In canSplit(start), return true at the end of the string, and return the stored answer if the slot for start holds one.
Otherwise try every word that starts at start, as in the plain recursion, and stop at the first one whose remainder can be cut.
Store the result in the slot, false included, and return it.
Return canSplit(0).

def wordBreak(s, wordDict):
    memo = [None] * len(s)  # memo[start]: answer for s[start:], None until worked out

    def can_split(start):
        if start == len(s):
            return True
        if memo[start] is not None:
            return memo[start]
        result = False
        for word in wordDict:
            if s.startswith(word, start) and can_split(start + len(word)):
                result = True
                break
        memo[start] = result
        return result

    return can_split(0)

Bottom-up over prefixes with a hash set

Intuition

Turn it around and work on prefixes. Let canEnd[i] say whether the first i letters can be cut into words. The empty prefix needs no words, so canEnd[0] is true. The first end letters can be cut exactly when their last piece, the letters from start to end, is a word and the letters before it can be cut, that is, canEnd[start] is true. Fill the table from left to right and every canEnd[start] you need is already known.

Instead of comparing all m words at each position, put the words in a hash set and look up the possible last pieces. No word is longer than L, so only the L pieces that end at end can match. On sunflowerseed, canEnd becomes true at 0, at 3 (sun), at 7 (flow), at 9 (flower) and at 13 (seed after position 9), so the answer is true. Position 7 leads nowhere, because no word starts with er, and the table does not care.

There are n positions, each looks up at most L pieces, and building and hashing a piece costs up to L steps. That is O(n × L²), at most 300 × 20 × 20 = 1.2 × 10^5 letter steps however large the dictionary is. Building the set reads every word once, O(m × L), so the total is O(m × L + n × L²). The set holds the words, O(m × L) letters, and the table n + 1 flags. There is no recursion.

Algorithm

Put every word in a hash set, and note the length L of the longest word.
Make canEnd with n + 1 entries, all false, and set canEnd[0] to true.
For each end from 1 to n, try each length from 1 to min(L, end).
If canEnd[end-length] is true and the piece of that length ending at end is in the set, set canEnd[end] to true and stop trying lengths.
Return canEnd[n].

def wordBreak(s, wordDict):
    words = set(wordDict)
    longest = max(len(word) for word in wordDict)
    n = len(s)
    # can_end[i]: the first i letters split into dictionary words
    can_end = [False] * (n + 1)
    can_end[0] = True  # the empty prefix needs no words
    for end in range(1, n + 1):
        # The last word is s[end-length:end], and no word is longer than longest.
        for length in range(1, min(longest, end) + 1):
            if can_end[end - length] and s[end - length:end] in words:
                can_end[end] = True
                break
    return can_end[n]

Pitfalls and edge cases

Most wrong answers come from committing to one cut too early, or from a search that never remembers its failures.

Cutting greedily. Taking the longest word first cuts carpetal as carpet and is left with al, though car + petal works. Taking the shortest first fails on sunflowerseed.
Checking only that every letter of s appears in some word. With the words aaaa and aa, every piece has an even length, so aaaaaaa, seven letters, cannot be cut.
Storing only the true answers in the memo. A true ends the search anyway. The repeated work is in the false branches, so a memo without them stays exponential.
Making the table one entry short. canEnd[i] is about the first i letters, and both 0 and n are valid, so it needs n + 1 entries.
Comparing past the end of s when a word is longer than what is left, such as the word abc against ab. Check the lengths before you compare letters.
In Lua and R, string positions start at 1: a piece of length k that ends at letter e starts at letter e-k+1.

Frequently asked questions4

What is the time complexity of Word Break?

The bottom-up table with a hash set runs in O(m × L + n × L²) time, where n is the length of s, m the number of words and L the longest word. Building the set reads every word once, and each of the n positions looks up at most L pieces of up to L letters. If you compare every word at every position instead, it is O(n × m × L). Plain recursion without a memo is exponential.

Why does a greedy approach fail for Word Break?

A greedy rule commits to one word and never reconsiders it. Longest first cuts carpetal into carpet and al, while car + petal works. Shortest first cuts sunflowerseed into sun + flow and gets stuck on erseed. Dynamic programming keeps every position that some cut can reach, so it never loses the right one.

Is Word Break a dynamic programming or a graph problem?

Both views work. As dynamic programming, canEnd[i] answers whether the first i letters can be cut, built from smaller prefixes. As a graph, every index is a node with an edge from i to j when the letters from i to j form a word, and you ask whether node n is reachable from node 0. A breadth-first search with a visited set does the same work as the table.

How do you list every sentence instead of returning true or false?

Use backtracking: at each index try every word that fits and recurse on the rest, building the sentence as you go. Remember the list of sentences for each index so a remainder is solved once. Run the true or false table first, so a string that cannot be cut skips the search. The number of sentences can grow exponentially, so the size of the output sets the running time.

Python

def wordBreak(s, wordDict):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "sunflowerseed"
wordDict = ["sun", "flow", "flower", "seed"]

Expected

true

Word Break

Function

Constraints

Examples

Hints

Solution

Try every word at every position

Recursion with a memo

Bottom-up over prefixes with a hash set

Pitfalls and edge cases

Frequently asked questions4

Similar problems