Word Break II
Asked at Oracle
Problem
Given a string s and a dictionary of strings wordDict, return an array of all valid sentences where s is segmented into a space-separated sequence of one or more dictionary words. You may return the answer in any order. Each word in the dictionary can be used multiple times.
Asked At
| Company | Difficulty | |
|---|---|---|
| Oracle | Hard | View all Oracle questions → |
How to Think About It
Try every prefix of the string and check if it exists in the dictionary.
For each valid prefix, recursively solve for the remaining substring.
Use memoization to cache results of subproblems to avoid recomputation.
Build a Trie from the dictionary for efficient prefix lookups.
Combine memoization with Trie pruning to achieve optimal backtracking performance.
Optimal Approach
The core idea is to use recursion with memoization. At each position i in string s, try every possible word ending position j. If the substring s[i..j] exists in the dictionary, recursively find all valid segmentations for s[j+1..n]. Memoize results for each starting index to avoid recomputation. Building a Trie from the dictionary allows early termination when no prefix matches, significantly pruning the search space. The time complexity is O(n * 2^n) in the worst case for generating all combinations, but memoization reduces repeated work on overlapping suffixes. Space complexity is O(n) for the recursion stack and memoization cache.
What Trips People Up in Real Interviews
Clarify whether the dictionary can contain duplicate words or if a word can be reused.
Start with the brute-force recursive solution to show understanding before optimizing.
Explain how memoization avoids redundant work on overlapping subproblems.
Discuss Trie-based pruning as a further optimization over plain hash set lookups.
Mention that output can be large and clarify time complexity in terms of total output size.
Solution Code
class Solution:
def wordBreak(self, s: str, wordDict: list[str]) -> list[str]:
word_set = set(wordDict)
memo = {}
def backtrack(start):
if start in memo:
return memo[start]
if start == len(s):
return []
results = []
for end in range(start + 1, len(s) + 1):
word = s[start:end]
if word in word_set:
if end == len(s):
results.append(word)
else:
for rest in backtrack(end):
results.append(word + " " + rest)
memo[start] = results
return results
return backtrack(0)Frequently Asked Questions
What is the Word Break II problem?
Given a string s and a dictionary of strings wordDict, return an array of all valid sentences where s is segmented into a space-separated sequence of one or more dictionary words. You may return the answer in any order. Each word in the dictionary can be used multiple times.
How do you solve Word Break II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Word Break II?
Word Break II is asked at Oracle. It is a hard difficulty problem.
What are common mistakes on Word Break II?
- Clarify whether the dictionary can contain duplicate words or if a word can be reused.
- Start with the brute-force recursive solution to show understanding before optimizing.
- Explain how memoization avoids redundant work on overlapping subproblems.
- Discuss Trie-based pruning as a further optimization over plain hash set lookups.
- Mention that output can be large and clarify time complexity in terms of total output size.