140. Word Break II
Asked at Oracle
Difficulty
Hard
Time
O(n * 2^n) worst case
Space
O(n) for the recursion stack plu
Pattern
Array
Companies
1
Problem
You are given a string s and a list of allowed words wordDict. Your job is to cut s into pieces so that every piece is a word from the dictionary, then join the pieces with single spaces to form a sentence. Return all such sentences.
A word from the dictionary may be used as many times as you like. The order of the sentences in your answer does not matter. If no valid cutting exists, return an empty list.
Every character of s must be used exactly once, and the cuts must follow the original order of characters — you cannot skip or reorder anything.
Cut the string into dictionary words
Constraints
- ●
1 <= s.length <= 20 - ●
1 <= wordDict.length <= 1000 - ●
1 <= wordDict[i].length <= 10 - ●
s and wordDict[i] consist of only lowercase English letters - ●
All the strings of wordDict are unique - ●
The total length of the answer does not exceed 10^5
Examples
s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]["cats and dog","cat sand dog"]s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]["pine apple pen apple","pineapple pen apple","pine applepen apple"]s = "catsandog", wordDict = ["cats","dog","sand","and","cat"][]Asked At
1 companies| 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.
Backtrack from each position, memoize the suffix
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
O(n * 2^n) worst case timeclass 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 runs in O(n * 2^n) worst case time and O(n) for the recursion stack plu space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.