Word Break II
Word Break II is a hard recursion & backtracking problem solved with the choice per position pattern.
The best approach, optimal (memoized dfs on suffixes), runs in O(n² + S · n) time and O(S · n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (backtracking) up.
Problem
You are given a string s and a list of distinct words wordDict. Insert spaces into s so that every piece is a word from the dictionary, and return all sentences you can build this way.
The same dictionary word may be used any number of times. Return the sentences in any order; if there is no way to split s, return an empty list.
Examples
Example 1
- Input
s = "sunflowerbed", wordDict = ["sun", "flower", "sunflower", "bed", "flowerbed"]- Output
["sun flower bed", "sun flowerbed", "sunflower bed"]- Why
- Three different ways split the string into dictionary words; the order of the sentences does not matter.
Example 2
- Input
s = "redcar", wordDict = ["red", "re", "dca", "car"]- Output
["red car"]- Why
- "re dca r" fails because "r" alone is not a word, so only one sentence works.
Example 3
- Input
s = "bluesky", wordDict = ["blue", "sk", "skies"]- Output
[]- Why
- After "blue", the rest "sky" cannot be built from the dictionary.
Constraints
1 <= s.length <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10sand every word consist only of lowercase English letters- All words in
wordDictare distinct - The total number of sentences in the answer does not exceed
10^5
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (backtracking) | O(2^n · n) | O(n) |
| Optimal (memoized DFS on suffixes) | O(n² + S · n) | O(S · n) |
1Brute force (backtracking)
O(2^n · n)In the worst case every one of the n - 1 gaps can be a split point, and each sentence costs O(n) to build; dead ends are explored again every time.O(n)Recursion depth and the current path are at most n (output not counted).Build sentences left to right. At position start, try every end index; if s[start..end) is a dictionary word, append it to the current path and recurse from end. When start reaches the end of the string, join the path into a sentence.
- Put the dictionary into a hash set.
- dfs(start, path): if start == n, add the joined path to the result.
- For end from start + 1 to n: if s[start..end) is in the set, push it, call dfs(end, path), pop it.
- Call dfs(0, []) and return the result.
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
List<String> result = new ArrayList<>();
dfs(s, 0, dict, new ArrayList<>(), result);
return result;
}
private void dfs(String s, int start, Set<String> dict, List<String> path, List<String> result) {
if (start == s.length()) {
result.add(String.join(" ", path));
return;
}
for (int end = start + 1; end <= s.length(); end++) {
String word = s.substring(start, end);
if (dict.contains(word)) {
path.add(word);
dfs(s, end, dict, path, result);
path.remove(path.size() - 1);
}
}
}
}class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
words = set(wordDict)
n = len(s)
result = []
path = []
def dfs(start: int) -> None:
if start == n:
result.append(' '.join(path))
return
for end in range(start + 1, n + 1):
word = s[start:end]
if word in words:
path.append(word)
dfs(end)
path.pop()
dfs(0)
return resultclass Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
vector<string> result, path;
dfs(s, 0, dict, path, result);
return result;
}
private:
void dfs(const string& s, int start, unordered_set<string>& dict, vector<string>& path, vector<string>& result) {
if (start == (int)s.size()) {
string sentence;
for (size_t i = 0; i < path.size(); i++) {
if (i) sentence += ' ';
sentence += path[i];
}
result.push_back(sentence);
return;
}
for (int end = start + 1; end <= (int)s.size(); end++) {
string word = s.substr(start, end - start);
if (dict.count(word)) {
path.push_back(word);
dfs(s, end, dict, path, result);
path.pop_back();
}
}
}
};function wordBreak(s, wordDict) {
const dict = new Set(wordDict);
const n = s.length;
const result = [], path = [];
const dfs = (start) => {
if (start === n) {
result.push(path.join(' '));
return;
}
for (let end = start + 1; end <= n; end++) {
const word = s.slice(start, end);
if (dict.has(word)) {
path.push(word);
dfs(end);
path.pop();
}
}
};
dfs(0);
return result;
}2Optimal (memoized DFS on suffixes)
O(n² + S · n)Each of the n suffixes tries n end positions once; S is the number of partial sentences built in total, each costing O(n) characters to concatenate.O(S · n)The memo stores every partial sentence for every suffix.Let solve(start) return every sentence that splits the suffix s[start..]. It depends only on start, so compute it once and cache it. For each dictionary word that is a prefix of the suffix, prepend the word to each sentence of solve(end). A suffix with no valid split is cached as an empty list, so dead ends are never explored twice.
- Put the dictionary into a hash set and create a memo map from start index to list of sentences.
- solve(n) = [""] (one empty sentence).
- solve(start): for each end in start+1..n with s[start..end) in the set, for each tail in solve(end), add word if tail is empty else word + ' ' + tail.
- Store the list in the memo and return it; the answer is solve(0).
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
Map<Integer, List<String>> memo = new HashMap<>();
return solve(s, 0, dict, memo);
}
private List<String> solve(String s, int start, Set<String> dict, Map<Integer, List<String>> memo) {
if (memo.containsKey(start)) return memo.get(start);
List<String> out = new ArrayList<>();
if (start == s.length()) {
out.add("");
} else {
for (int end = start + 1; end <= s.length(); end++) {
String word = s.substring(start, end);
if (!dict.contains(word)) continue;
for (String tail : solve(s, end, dict, memo)) {
out.add(tail.isEmpty() ? word : word + " " + tail);
}
}
}
memo.put(start, out);
return out;
}
}class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
words = set(wordDict)
n = len(s)
memo = {}
def solve(start: int) -> List[str]:
if start in memo:
return memo[start]
out = []
if start == n:
out.append('')
else:
for end in range(start + 1, n + 1):
word = s[start:end]
if word not in words:
continue
for tail in solve(end):
out.append(word if tail == '' else word + ' ' + tail)
memo[start] = out
return out
return solve(0)class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
unordered_map<int, vector<string>> memo;
return solve(s, 0, dict, memo);
}
private:
vector<string> solve(const string& s, int start, unordered_set<string>& dict, unordered_map<int, vector<string>>& memo) {
auto it = memo.find(start);
if (it != memo.end()) return it->second;
vector<string> out;
if (start == (int)s.size()) {
out.push_back("");
} else {
for (int end = start + 1; end <= (int)s.size(); end++) {
string word = s.substr(start, end - start);
if (!dict.count(word)) continue;
for (const string& tail : solve(s, end, dict, memo)) {
out.push_back(tail.empty() ? word : word + " " + tail);
}
}
}
memo[start] = out;
return out;
}
};function wordBreak(s, wordDict) {
const dict = new Set(wordDict);
const n = s.length;
const memo = new Map();
const solve = (start) => {
if (memo.has(start)) return memo.get(start);
const out = [];
if (start === n) {
out.push('');
} else {
for (let end = start + 1; end <= n; end++) {
const word = s.slice(start, end);
if (!dict.has(word)) continue;
for (const tail of solve(end)) {
out.push(tail === '' ? word : word + ' ' + tail);
}
}
}
memo.set(start, out);
return out;
};
return solve(0);
}Edge cases to test
- No valid split at all: return an empty list
- The whole string is a single dictionary word
- A dictionary word can be reused many times, like s = "aaaa" with ["a", "aa"]
- Many dead-end prefixes that fail only at the last character
Hints
Hint 1
Try every dictionary word that is a prefix of the remaining string, then recurse on what is left.
Hint 2
The same suffix of s is reached through many different prefixes. Its list of sentences never changes.
Hint 3
Memoize: for each start index, store the list of sentences that split s[start..].
FAQ
What is the best time complexity for Word Break II?
Optimal (memoized DFS on suffixes) runs in O(n² + S · n) time and O(S · n) extra space. Each of the n suffixes tries n end positions once; S is the number of partial sentences built in total, each costing O(n) characters to concatenate.
Which pattern does Word Break II use?
It is a recursion & backtracking problem that uses the choice per position pattern. Other problems with the same pattern: Letter Combinations of a Phone Number, Confusing Number II, Strobogrammatic Number II.
Is there a brute force solution for Word Break II?
Yes. Brute force (backtracking) takes O(2^n · n) time and O(n) space. Build sentences left to right.
Which edge cases should I test for Word Break II?
No valid split at all: return an empty list; The whole string is a single dictionary word; A dictionary word can be reused many times, like s = "aaaa" with ["a", "aa"]; Many dead-end prefixes that fail only at the last character.