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²) , where n is the length of s , m the number of words and L the longest word. Comparing every word at every position costs O(n × m × L) . Plain recursion is exponential.

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

Both. As dynamic programming, canEnd[i] says whether the first i letters can be cut. As a graph, each index is a node, with an edge from i to j when the letters between them form a word, and you ask whether n is reachable from 0. A breadth-first search 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 that are all words 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 leaves er, which no word starts, 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: Both pine + apple and pineapple leave tart. Only tar fits there, which leaves a lone t, so no cut works.

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

Committing to one word at a time fails, and trying every cut is exponential. But whether the rest of s can be cut depends only on where it starts, so there are only n + 1 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

The first piece must be a word that s starts with. Try each such word and ask the same question about the letters that remain; an empty remainder means every letter is cut. Trying every first word, then every second word, cannot miss a valid cut.

It checks the same remainders over and over. With 299 copies of a followed by one b, and the words a, aa up to ten as, more than 10^89 ways to cut the a's into blocks reach the b and fail, and the recursion tries them all.

Algorithm

Write canSplit(start): can the letters from start to the end be cut? If start equals the length of s, return true.
For each word that s contains at index start, if canSplit(start + its length) is true, return true.
Otherwise 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 start, which takes n + 1 values. In the a's example, the remainder at index 20 is reached after two blocks of ten, after twenty single as and in countless other ways, and is false each time. Store each start's answer once and reuse it.

The memo must keep the false answers. A true ends the whole search at once, so all the repeated work is in branches that fail.

Each start tries every word, comparing up to L letters: O(n × m × L) time, at most 6 × 10^6 letter checks, and O(n) space.

Algorithm

Make a memo with one slot per index, each marked as not worked out.
In canSplit(start), return true at the end of s, or the stored answer if the slot holds one.
Otherwise try every word as in the plain recursion, store the result in the slot, false included, and return it.

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

Work on prefixes. Let canEnd[i] say whether the first i letters can be cut; canEnd[0] is true, since the empty prefix needs no words. The first end letters can be cut exactly when their last piece, from start to end, is a word and canEnd[start] is true. Filled from left to right, every canEnd[start] you need is already known.

Put the words in a hash set. No word is longer than L, so only the L pieces that end at end can match, however large the dictionary. On sunflowerseed, canEnd is true at 0, 3, 7, 9 and 13; the dead end at 7 does no harm.

Each of n positions looks up at most L pieces, each costing up to L steps to build and hash: O(n × L²), at most 1.2 × 10^5 steps, plus O(m × L) for the set.

Algorithm

Put the words in a hash set; note the longest length L.
Make canEnd with n + 1 entries, all false, and set canEnd[0] to true.
For each end from 1 to n and 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.
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

Cutting greedily. Longest first cuts carpetal as carpet and strands al, though car + petal works; shortest first gets stuck on sunflowerseed.
Storing only the true answers in the memo. The repeated work is in the false branches, so the a's example stays exponential.
Making the table one entry short. canEnd needs n + 1 entries, for prefix lengths 0 to n.
Comparing past the end of s, such as the word abc against the remainder ab. Check the lengths first.
In Lua and R, string positions start at 1: a piece of length k ending at letter e starts at e-k+1.

Frequently asked questions3

What is the time complexity of Word Break?

The bottom-up table with a hash set runs in O(m × L + n × L²), where n is the length of s, m the number of words and L the longest word. Comparing every word at every position costs O(n × m × L). Plain recursion is exponential.

Is Word Break a dynamic programming or a graph problem?

Both. As dynamic programming, canEnd[i] says whether the first i letters can be cut. As a graph, each index is a node, with an edge from i to j when the letters between them form a word, and you ask whether n is reachable from 0. A breadth-first search does the same work as the table.

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

Backtrack: at each index try every word that fits, recurse on the rest, and remember the list of sentences for each index. 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 output size sets the running time.

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

Test #1

Test #2

Test #3

Arguments

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

Expected Output

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 questions3

Similar problems