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.
This approach utilizes recursion to explore all possible partitions of the string, while memoization stores the results of subproblems to avoid redundant computations. We start from the first character, continuously check substrings against the dictionary, and recursively process the remaining parts of the string. The solutions for these parts are combined to form complete sentences. Memoization optimizes this by caching results of repeating subproblems.
The function wordBreak initiates the recursive backtrack function starting from index 0. The backtrack function attempts to form words by iterating over possible substrings. If a substring is found in the wordDict, it recursively attempts to formulate sentences with the rest of the string. Results of each position are stored in memo to avoid recalculations.
Python
JavaScript
C
Time Complexity: O(n^3), where n is the length of the input string, due to substring operations and memoization.
Space Complexity: O(n^3), for memoization of results and recursion stack.
This method uses dynamic programming to dynamically determine all possible sentences from the string based on the dictionary. We iterate through the string and for each suffix, if a word ends at the current position, all sentences that lead up to this word are combined with the word to form new valid sentences. A 2D list keeps track of sentences possible up to each character index.
The Java solution uses a list of lists dp where dp[i] holds all possible sentences that can be formed up to index i. By iterating over every substring, sentences are built incrementally and stored up to each index. Each word ending at index i is checked, and if valid, sentences are built by appending the word to sentences from the previous indexes.
Time Complexity: O(n^3), because of substring operations and iteration over previous results.
Space Complexity: O(n^3), for the storage of all potential sentences in a 2D list.
| Approach | Complexity |
|---|---|
| Backtracking with Memoization | Time Complexity: O(n^3), where n is the length of the input string, due to substring operations and memoization. |
| Dynamic Programming | Time Complexity: O(n^3), because of substring operations and iteration over previous results. |
| Default Approach | — |
| 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 |
Word Break 2 | Leetcode #140 • Techdose • 35,369 views views
Watch 9 more video solutions →Practice Word Break II with our built-in code editor and test cases.
Practice on FleetCode