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.
1def wordBreak(s, wordDict):
2 def backtrack(start):
3 if start in memo:
4 return memo[start]
5 res = []
6 if start == len(s):
7 return ['']
8 for end in range(start + 1, len(s) + 1):
9 word = s[start:end]
10 if word in wordDict:
11 for sub_sentence in backtrack(end):
12 if sub_sentence:
13 res.append(word + ' ' + sub_sentence)
14 else:
15 res.append(word)
16 memo[start] = res
17 return res
18 memo = {}
19 return backtrack(0)
20
21# Example Usage
22s = "catsanddog"
23wordDict = {"cat", "cats", "and", "sand", "dog"}
24print(wordBreak(s, wordDict))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.
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.