Word Break II

Word Break II takes the classic "can this string be split into dictionary words" question and asks for every way to do it. It is a perfect lesson in DFS that returns built-up answers, plus memoizing on a suffix so the recursion does not explode.

The slow way first

You could try every possible set of cut points: between each pair of characters, decide to split or not. That is 2^n combinations for a length-n string, and you still have to check each piece against the dictionary. Way too slow.

The better question: standing at some index start, what sentences begin here? Every valid sentence starts with some dictionary word that prefixes s[start:], followed by a valid sentence for the rest. That is a recursive definition — exactly what DFS is for.

The idea: DFS over prefixes, memo on the suffix

From index start, scan every prefix s[start:end]. If that prefix is a dictionary word, recurse on dfs(end) to get all sentences for the remaining suffix, and glue the word onto the front of each. The base case is start == len(s): an empty suffix yields one empty sentence [""].

The catch: the same suffix gets solved over and over (think "aaaa..."). So we memoize: memo[start] stores the full list of sentences that start at that index. The second time we ask, we return it instantly.

The key insight: we build answers bottom-up through the return values. Each call hands its caller a list of complete suffixes, and the caller prepends its word to all of them.

Walk through it

Step through the animation. The start pointer marks where the current suffix begins. From start = 0, the prefix "cat" matches, so we recurse on "sand"; "sand" consumes the rest, hitting the empty base case which returns [""]. Prepending gives "cat sand". Back at 0, the longer prefix "cats" also matches, recursing on "and" to give "cats and". Two sentences total.

Pseudocode

memo = empty map        # start index -> list of sentences
function dfs(start):
    if start == length of s:
        return [""]                       # empty suffix: one empty sentence
    if start in memo:
        return memo[start]                # already solved this suffix
    out = []
    for end from start+1 to length of s:
        word = s[start:end]
        if word is in the dictionary:
            for rest in dfs(end):         # all sentences for the suffix
                add (word + " " + rest) to out
    memo[start] = out
    return out
return dfs(0)

The Python solution

def word_break(s, words):
    memo = {}
    def dfs(start):
        if start == len(s):
            return [""]
        if start in memo:
            return memo[start]
        out = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in words:
                for rest in dfs(end):
                    out.append((word + " " + rest).strip())
        memo[start] = out
        return out
    return dfs(0)

• memo maps a start index → the list of sentences that can be built from s[start:].
• The base case start == len(s) returns [""]: a single empty sentence so the caller has something to prepend onto.
• The memo check returns a cached list immediately — this is what turns exponential work into polynomial.
• The loop tries every prefix s[start:end]; if it is a dictionary word we recurse on end.
• (word + " " + rest).strip() glues the word to each suffix sentence; .strip() removes the trailing space when rest is empty.

Complexity

The memo bounds how often each suffix is solved, but the output itself can be large — there can be exponentially many sentences, so building and storing them is the real cost. Memoization removes the redundant recomputation, not the inherent size of the answer.

When this pattern shows up

Practice