Word Break II LeetCode 140 Guide

LeetCode 140 — Word Break II — gives you a string s and a dictionary of strings wordDict. Your task is to add spaces in s to construct a sentence where each word is a valid dictionary word, and return all such possible sentences in any order. Unlike Word Break I (LeetCode 139), which only asks if a valid segmentation exists, Word Break II requires you to enumerate every valid segmentation explicitly.

For example, given s = "catsanddog" and wordDict = ["cat","cats","and","sand","dog"], the output is ["cats and dog", "cat sand dog"]. Both segmentations cover all characters of s with words from the dictionary. If no valid segmentation exists, return an empty list. The problem is harder than it looks because the number of valid sentences can be exponentially large in the worst case.

The challenge combines two algorithmic ideas: feasibility checking (can the string be broken?) and path enumeration (list all ways to break it). Pure dynamic programming from Word Break I answers the first question efficiently but cannot enumerate paths without major extension. The right approach is backtracking guided by the dictionary, with memoization to avoid redundant work on repeated suffixes.

Word Break I (LeetCode 139) is a classic 1-D DP problem. Build a boolean array dp where dp[i] is true if the substring s[0:i] can be segmented into dictionary words. Fill it left to right: for each position i, check every j < i such that dp[j] is true and s[j:i] is in the dictionary. If any such j exists, set dp[i] = true. The answer is dp[len(s)].

This DP tells you whether a valid segmentation exists but gives no information about which prefixes were chosen at each step. Reconstructing all paths from a feasibility DP requires storing backtracking links at every position, which essentially transforms the DP into the full memoized backtracking solution anyway. It is cleaner and more intuitive to go directly to backtracking for Word Break II.

The transition from I to II is conceptual: shift from "can we reach the end?" to "what are all the routes to the end?" Backtracking answers the second question naturally — at each position, try every prefix that is a dictionary word, recurse on the remaining suffix, and collect results. Memoization is the efficiency layer that prevents the same suffix from being re-solved from scratch each time it is reached via different prefixes.

The backtracking function takes a start index and returns all valid sentences that can be formed from s[start:]. Base case: when start equals len(s), return a list containing one empty string — the sentinel that signals a complete segmentation has been reached. Recursive case: try every end index from start+1 to len(s)+1; if s[start:end] is in the dictionary, recurse on end to get all sentences for the remaining suffix, then prepend s[start:end] to each suffix sentence.

Combining prefix word with suffix results is straightforward: if the current word is "cat" and the suffix returns ["sand dog"], produce "cat sand dog". If start == len(s) the base case returns [""], and "cat" combined with "" produces "cat" — which is handled by checking if the suffix sentence is empty and omitting the extra space. This keeps the combination logic clean and uniform across all recursion levels.

The time complexity without memoization is O(n * 2^n) in the worst case — for a string like "aaa...a" with dictionary ["a","aa","aaa",...], nearly every prefix is valid and the tree fans out exponentially. With memoization, repeated suffix calls are resolved in O(1) and the total work is proportional to the size of the output, which is bounded but can still be exponential when the answer set is large.

The key observation that motivates memoization is that different prefixes can lead to the same suffix. For s = "catsanddog", both "cat" and "cats" are valid first words. After choosing "cat", the suffix is "sanddog" starting at index 3. After choosing "cats", the suffix is "anddog" starting at index 4. These are different suffixes, so no sharing here. But in a string like "aaa" with dictionary ["a","aa"], "a|aa" and "aa|a" both leave the same suffix "" at different points — and in longer strings the overlap grows rapidly.

Memoization stores the list of sentences for each start index after the first time it is computed. On subsequent calls with the same start, return the cached list immediately. In Python this is most elegantly expressed with @functools.lru_cache on the backtrack function, or with a memo dictionary keyed by start index. In Java, use a HashMap<Integer, List<String>> initialized before the recursive method.

The memoized solution avoids redundant work at the cost of extra memory for the cache. In the worst case the cache holds O(n) entries, each containing a list of sentences. The total memory is proportional to the total size of all cached sentence lists, which is bounded by the output size. For inputs with large valid sentence sets the memory can be substantial, but that is unavoidable — any algorithm must produce the full output.

The first step in any implementation is converting wordDict from a list to a set. List membership checking is O(k) where k is the dictionary size; set lookup is O(1) average case. Inside the backtracking loop, s[start:end] is tested against the dictionary at every position for every recursive call, so the lookup cost compounds quickly. Using a set ensures that dictionary checks do not become the bottleneck.

Try all prefix lengths from 1 to len(s) - start. For each candidate prefix s[start:end], check membership in the word set. Only recurse when the prefix is a valid word — this is the pruning step that keeps the backtracking tree manageable. Early pruning is especially effective when the dictionary is small relative to the string length, because most prefixes will fail the membership check and their subtrees are never explored.

An additional optimization is to limit the maximum prefix length to the longest word in the dictionary. If no word in wordDict exceeds 10 characters (the constraint ceiling), then end - start never needs to exceed 10. Instead of looping end from start+1 to len(s)+1, loop end from start+1 to min(start + max_word_len + 1, len(s) + 1). This caps the inner loop at a constant factor and can dramatically reduce work when the string is long but dictionary words are short.

In Python, define wordBreak(s, wordDict) with wordSet = set(wordDict). Use @functools.lru_cache(None) on an inner function backtrack(start) that returns a tuple of sentences (tuples are hashable, required for lru_cache). Base case: return ("",) when start == len(s). Inner loop tries s[start:end] for end in range(start+1, len(s)+1); for each valid word, join it with each suffix sentence and collect. Convert the final result from backtrack(0) to a list, filtering out the lone empty string. Time complexity is O(n * 2^n) worst case, but memoization prunes heavily in practice.

In Java, declare a HashMap<Integer, List<String>> memo. The private List<String> backtrack(String s, Set<String> wordSet, int start, Map<Integer, List<String>> memo) method checks memo first and returns immediately if the key exists. Otherwise, create a new ArrayList<String> result. If start == s.length(), add "" and put result in memo, then return. Loop end from start+1 to s.length()+1: if wordSet.contains(s.substring(start, end)), recurse on end and combine. Store result in memo before returning. Call backtrack(s, wordSet, 0, memo) from the public method.

Both implementations share the same structure: convert dict to set, memoize by start index, base case returns [""] at the end of the string, and combination joins prefix word with suffix sentences using a space. The join logic handles the empty-string base case by returning just the word when the suffix is "". The overall algorithm is correct by induction: if backtrack(end) returns all valid sentences from s[end:], then prepending s[start:end] to each gives all valid sentences from s[start:].

Word Break I (LeetCode 139) is the natural prerequisite. Mastering the 1-D DP feasibility check first builds intuition for why backtracking is needed for II — the DP proves reachability but cannot enumerate routes. Revisiting Word Break I after solving II deepens understanding of when DP alone suffices versus when path reconstruction requires backtracking or explicit DP-with-parent-pointers.

Palindrome Partitioning (LeetCode 131) has an identical algorithmic shape: partition a string into substrings satisfying a property (palindrome vs. in-dictionary) and return all valid partitions. The backtracking template is the same; only the validity check differs. Solving both problems side-by-side reveals how the "partition a string with a validity predicate" pattern generalizes across problem families.

Subsets II (LeetCode 90) and other backtracking enumeration problems round out the skill set. The core pattern — make a choice, recurse, undo the choice, skip invalid branches early — appears throughout the backtracking family. Memoization by subproblem state (start index for Word Break II, current path for subsets) is the scalability layer that converts exponential brute force into tractable enumeration. Recognizing this pattern unlocks a wide class of hard LeetCode problems.