Word Break II

Problem

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Examples

The brute-force approach

DFS: at each position, try every word in the dictionary. If the word matches the current prefix, recurse from the end of that word.

words = set(wordDict)
result = []
def dfs(start, path):
    if start == len(s):
        result.append(" ".join(path))
        return
    for end in range(start+1, len(s)+1):
        if s[start:end] in words:
            path.append(s[start:end])
            dfs(end, path)
            path.pop()
dfs(0, [])

Exponential without memoization — same suffix is explored multiple times.

Spotting the pattern

This is a Memoization problem. The key question to ask yourself:

When you memoize dfs(start), what does the cached value represent? Why can different call paths benefit from the same cached result?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.