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.Word Break II requires generating all valid sentences by inserting spaces into a string such that every word exists in a given dictionary. A common strategy combines backtracking with memoization. The idea is to recursively try every prefix of the string and check whether it exists in a dictionary stored in a HashSet. When a valid prefix is found, the algorithm recursively solves the remaining substring and appends results to build full sentences.
Since naive recursion recomputes the same substrings multiple times, memoization is used to cache previously computed results for each index or substring. This dramatically reduces repeated work and makes the solution practical. In some implementations, a Trie can be used to efficiently check valid prefixes while exploring possibilities.
The challenge lies in handling the potentially large number of sentence combinations. With memoization, the algorithm avoids redundant computation while systematically exploring all valid segmentations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with Memoization | O(N * 2^N) in worst case due to sentence generation | O(N * 2^N) for storing combinations and recursion stack |
| Backtracking with Trie Optimization | O(N * 2^N) | O(N * 2^N) plus Trie storage |
NeetCode
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.
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.
1var wordBreak = function(s, wordDict) {
2 const memo = {};
3 function backtrack(start) {
4 if (start in memo) return memo[start];
5 const res = [];
6 if (start === s.length) return [''];
7 for (let end = start + 1; end <= s.length; end++) {
8 const word = s.substring(start, end);
9 if (wordDict.has(word)) {
10 const subsentences = backtrack(end);
11 for (const subsentence of subsentences) {
12 res.push(subsentence.length ? word + ' ' + subsentence : word);
13 }
14 }
15 }
16 memo[start] = res;
17 return res;
18 }
19 return backtrack(0);
20};
21
22// Example Usage
23const s = "catsanddog";
24const wordDict = new Set(["cat", "cats", "and", "sand", "dog"]);
25console.log(wordBreak(s, wordDict));The function wordBreak uses a closure backtrack to recursively find all valid sentences starting from each index of the string. For each starting index, it checks substrings against wordDict and attempts to form complete sentences using the rest of the string. Results are memoized to avoid recomputation.
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.
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.
1import java.util.*;
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the Word Break problems are commonly asked in technical interviews, including FAANG companies. They test understanding of dynamic programming, recursion, and optimization techniques like memoization.
A HashSet is typically used to store dictionary words for O(1) lookups. In some optimized solutions, a Trie can also be used to efficiently match prefixes while exploring the string.
Without memoization, the recursion repeatedly solves the same substrings, leading to exponential recomputation. Memoization stores the results of each substring so future calls can reuse them, reducing redundant work.
The most common optimal approach combines backtracking with memoization. It recursively tries valid prefixes and caches results for previously solved substrings to avoid recomputation. This significantly improves performance compared to naive recursion.
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.