Watch 10 video solutions for Word Break II, a hard level problem involving Array, Hash Table, String. This walkthrough by Techdose has 35,369 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] Output: ["cats and dog","cat sand dog"]
Example 2:
Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"] Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"] Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: []
Constraints:
1 <= s.length <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10s and wordDict[i] consist of only lowercase English letters.wordDict are unique.Problem Overview: You receive a string s and a dictionary of valid words. The goal is to return every possible sentence that can be formed by inserting spaces in s so that each segment exists in the dictionary. Unlike the classic Word Break problem, this version requires generating all valid combinations, not just checking feasibility.
Approach 1: Backtracking with Memoization (Time: O(2^n), Space: O(n * 2^n))
The natural way to build sentences is recursive backtracking. Start from index 0, try every possible prefix, and check if the substring exists in a dictionary stored in a HashSet. If the prefix is valid, recursively solve the remaining suffix and append the current word in front of each returned sentence. Without optimization this becomes extremely slow because the same suffix is recomputed many times. Memoization fixes this: store results for each starting index so future calls reuse previously generated sentences. The recursion tree shrinks dramatically because each substring is processed once. This technique combines backtracking with memoization, making it the most practical solution when the number of valid sentences is manageable.
Approach 2: Dynamic Programming Sentence Construction (Time: O(n^2 + total_sentences), Space: O(n * total_sentences))
A bottom-up dynamic programming approach builds valid sentences ending at every index. Maintain a DP array where dp[i] stores all sentences that form the substring s[0:i]. Iterate through each index i, then check every earlier split j. If s[j:i] is a dictionary word and dp[j] already contains valid sentences, append the word to each sentence in dp[j]. Store the results in dp[i]. This effectively converts the segmentation problem into a sentence-building pipeline. A hash table speeds up dictionary lookups to O(1). While the DP avoids recursion, memory usage can grow quickly because it stores all intermediate sentence combinations.
Recommended for interviews: Backtracking with memoization is the approach most interviewers expect. It demonstrates strong understanding of recursion, pruning, and caching repeated subproblems. Starting with naive backtracking shows you understand the search space, then adding memoization proves you can optimize exponential recursion using dynamic programming principles.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking (Naive) | O(2^n) | O(n) | Conceptual starting point to explore all splits; impractical for large inputs |
| Backtracking with Memoization | O(2^n) | O(n * 2^n) | Preferred interview solution; avoids recomputing suffix results |
| Bottom-Up Dynamic Programming | O(n^2 + total_sentences) | O(n * total_sentences) | Useful when building sentences iteratively or avoiding recursion depth limits |