Word Break II

Table of Contents +

You get a long string with no spaces, like catsanddog. You also get a list of real words. The question asks you to add spaces so the string breaks into real words, and you must find every way to do it. This is like how a phone keyboard guesses where one word ends and the next begins. The hard part is that the same string can split in several valid ways, and you have to return all of them.

🎯 The Problem

You get a string and a dictionary, which is a list of valid words. You must split the string into sentences of dictionary words.

  • Break the string so every word comes from the dictionary.
  • Return every such sentence, not just one.
  • A dictionary word may be used more than once.
  • The order of the sentences does not matter.
  • For catsanddog with cat, cats, and, sand, dog, there are two ways to split it.
Input:  s = "catsanddog"
        words = ["cat", "cats", "and", "sand", "dog"]
Output: ["cat sand dog", "cats and dog"]


Explanation: "cats" + "and" + "dog"
         and "cat"  + "sand" + "dog"

You return all valid sentences in any order.

This diagram shows the two valid split points near the start of the string.

cat

cats

sand

and

dog

dog

catsanddog

sanddog

anddog

dog

dog

cat sand dog

cats and dog

🐢 Approach 1: Plain Backtracking Without Memory (Brute Force)

The idea in one line: try every prefix as a word, then solve the rest the same way.

The idea:

  • Backtracking means try a split, go deeper, and step back to try another.
  • Start at the front of the string and try every prefix.
  • A prefix is a starting chunk of the string.

How it works:

  • If a prefix is a dictionary word, cut it off and solve the rest the same way.
  • When you reach the end, the words you picked form one valid sentence.

Why it is weak:

  • The same leftover string gets solved again and again.
  • Say two prefixes both lead to the leftover dog. It solves dog twice.
  • For long strings with many splits, the repeated work makes the time blow up.

Here is the plain backtracking code:

word_break_ii_plain_backtracking.py
def word_break(s, word_dict):
    words = set(word_dict)
    result = []


    def dfs(index, path):
        if index == len(s):
            result.append(" ".join(path))
            return
        for end in range(index + 1, len(s) + 1):
            word = s[index:end]
            if word in words:
                dfs(end, path + [word])


    dfs(0, [])
    return result

⚡ Approach 2: Backtracking With Memoization (Best)

The idea in one line: solve each leftover once and remember its sentences in a cache.

The idea:

  • Memoization means remember the answer for a piece of work so you never redo it.
  • The piece of work here is “all sentences for the leftover starting at index i”.
  • Store that list in a cache keyed by the index.

How it works:

  • Before solving a leftover, check the cache.
  • If this exact leftover was already solved, return the saved list right away.
  • If not, solve it once, save the list, and return it.
  • Try each end position from the current index. The chunk to that end is a candidate word.
  • If the chunk is in the dictionary, recurse on the rest, then glue this word in front of every sentence the rest returns.

Why it is fast:

  • Each starting index is solved a single time.
  • The sentences for a leftover never change, no matter how you reached it.
  • So reaching the same leftover again just reads the cache.

This diagram shows how memoization reuses the answer for the leftover dog. Both paths reach dog, but we solve it only once.

path cat + sand

leftover dog at index 7

path cats + and

solve once: returns dog

cache index 7 -> dog

cat sand dog

cats and dog

Steps to Solve

  1. Put the dictionary words into a set for instant lookup.
  2. Write a function that returns all sentences for the substring starting at a given index.
  3. If that index is the end of the string, return a list with one empty sentence to stop the recursion.
  4. Check the cache for this index. If it is there, return the saved list.
  5. Try every end position after the index. Take the chunk from the index to that end as a candidate word.
  6. If the chunk is in the dictionary, solve the rest, then attach this word in front of every returned sentence.
  7. Save the collected sentences in the cache for this index and return them.

This Python version uses a set for the dictionary and a dictionary as the memo cache keyed by the start index.

word_break_ii.py
def word_break(s, words):
    word_set = set(words)   # instant lookup
    memo = {}               # index -> list of sentences


    def solve(start):
        if start in memo:               # already solved this leftover
            return memo[start]
        if start == len(s):
            return [""]                 # one empty sentence to stop recursion
        sentences = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]         # candidate chunk
            if word in word_set:
                for rest in solve(end): # all sentences for the leftover
                    if rest == "":
                        sentences.append(word)
                    else:
                        sentences.append(word + " " + rest)
        memo[start] = sentences         # save for this index
        return sentences


    return solve(0)




s = "catsanddog"
words = ["cat", "cats", "and", "sand", "dog"]
print(word_break(s, words))

The output of the above code will be:

['cat sand dog', 'cats and dog']

Let us read the Python version line by line and see why the cache matters.

The line word_set = set(words) turns the word list into a set. A set gives almost instant lookups, so checking if a chunk is a real word is fast. The line memo = {} is the cache. Its key is a start index. Its value is the full list of sentences for the substring starting there.

Inside solve, the line if start in memo is the speedup. If we already solved the leftover starting at this index, we hand back the saved list and skip all the work. This is what stops the repeated solving of the same leftover.

The line if start == len(s) is the base case. When we reach the end, we return a list holding one empty string. That empty string is a clever signal. It means “there is exactly one way to finish from here, with nothing left to add”. The caller will glue a word in front of it.

The loop for end in range(start + 1, len(s) + 1) tries every chunk length. The line word = s[start:end] cuts the chunk. The line if word in word_set keeps only chunks that are real words.

For a valid word, for rest in solve(end) gets every sentence for the leftover. The check if rest == "" handles the last word. When the rest is the empty string, we just keep the word with no trailing space. Otherwise we join the word and the rest with a space. The line memo[start] = sentences saves the result before returning, so the next time anyone asks for this index, the answer is ready.

⏱️ Time and Space Complexity

Plain backtracking can repeat the same leftover many times, so its time grows fast, close to two to the power of n in the worst case, where n is the length of the string. Memoization solves each start index once, so the work per index is bounded by the string length and the number of sentences it produces. The space holds the cache, which stores a list of sentences for each index.

Approach Time Complexity Space Complexity
Plain backtracking O(2^n) worst case O(n) recursion depth
Backtracking with memoization O(n^2 + sentences) much faster O(n * sentences) for the cache

Tip

The point of memoization is simple. The sentences for a leftover never change, no matter how you reached that leftover. So solve each leftover once and store it. Reaching it again just reads the cache.

🧩 Key Takeaways

  • ✅ Try every prefix as a word, and if it is in the dictionary, solve the rest.
  • ✅ At the end of the string, return a single empty sentence to stop the recursion.
  • ✅ Glue each valid word in front of every sentence the rest returns.
  • ✅ Cache the sentences per start index so you never solve the same leftover twice.
  • ✅ Put the words in a set for instant lookups.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What does Word Break II return?

    Why: Word Break II returns all valid sentences, not just whether a split exists.

  2. 2

    Why does memoization speed up the solution?

    Why: The sentences for a leftover are the same no matter how you reached it, so we cache them by index.

  3. 3

    What does returning a list with one empty string at the end of the string mean?

    Why: The empty sentence is a base case signal so the caller can attach a word in front of it.

  4. 4

    Why store the dictionary words in a set?

    Why: A set gives near constant time membership checks, so testing each chunk is fast.

Score: 0 / 4

🚀 What’s Next?

Previous Sudoku Solver Next Jump Game