Word Break II solution and explanation
Google
9 more videos on this problem
Word Break 2 | Leetcode #140Techdose · 18:41 · 35K views
Word Break II - Leetcode 140 - PythonNeetCodeIO · 20:39 · 30K views
Word Break ii | LeetCode 140 | C++, PythonKnowledge Center · 19:50 · 19K views
Word Break II | 2 Recursion Approaches | Backtracking | Memoization | Tree Diagram | Leetcode 140codestorywithMIK · 38:26 · 16K views
WORD BREAK II | LEETCODE # 140 | PYTHON DFS SOLUTIONCracking FAANG · 21:20 · 7K views
Understand LeetCode 140. Word Break II in 4 minutesWasabi Studio · 3:19 · 7K views
140. Word Break II | Word Break 2 | Dynamic Programming | BacktrackingAryan Mittal · 31:32 · 5K views
Leetcode - Word Break II (Python)Timothy H Chang · 12:49 · 2K views
[Java] Leetcode 140. Word Break II [DP Subsequence #8]Eric Programming · 17:32 · 2K views
Word Break II | Day 30 | DP Memoization [ July LeetCoding Challenge ] [ Leetcode #140 ] [ 2020 ]Algorithms Made Easy · 5:01 · 2K views
The problem
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 <= 10sandwordDict[i]consist of only lowercase English letters.- All the strings of
wordDictare unique. - Input is generated in a way that the length of the answer doesn't exceed 105.
Approach overview
Problem Overview: You receive a string s and a dictionary of valid words. The goal is to return every possible sentence that can be formed by inserting spaces in s so that each segment exists in the dictionary. Unlike the classic Word Break problem, this version requires generating all valid combinations, not just checking feasibility.
Approach 1: Backtracking with Memoization (Time: O(2^n), Space: O(n * 2^n))
The natural way to build sentences is recursive backtracking. Start from index 0, try every possible prefix, and check if the substring exists in a dictionary stored in a HashSet. If the prefix is valid, recursively solve the remaining suffix and append the current word in front of each returned sentence. Without optimization this becomes extremely slow because the same suffix is recomputed many times. Memoization fixes this: store results for each starting index so future calls reuse previously generated sentences. The recursion tree shrinks dramatically because each substring is processed once. This technique combines backtracking with memoization, making it the most practical solution when the number of valid sentences is manageable.
Approach 2: Dynamic Programming Sentence Construction (Time: O(n^2 + total_sentences), Space: O(n * total_sentences))
A bottom-up dynamic programming approach builds valid sentences ending at every index. Maintain a DP array where dp[i] stores all sentences that form the substring s[0:i]. Iterate through each index i, then check every earlier split j. If s[j:i] is a dictionary word and dp[j] already contains valid sentences, append the word to each sentence in dp[j]. Store the results in dp[i]. This effectively converts the segmentation problem into a sentence-building pipeline. A hash table speeds up dictionary lookups to O(1). While the DP avoids recursion, memory usage can grow quickly because it stores all intermediate sentence combinations.
Recommended for interviews: Backtracking with memoization is the approach most interviewers expect. It demonstrates strong understanding of recursion, pruning, and caching repeated subproblems. Starting with naive backtracking shows you understand the search space, then adding memoization proves you can optimize exponential recursion using dynamic programming principles.
Approach 1: Backtracking with Memoization
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.
def wordBreak(s, wordDict):
def backtrack(start):
if start in memo:
return memo[start]
res = []
if start == len(s):
return ['']
for end in range(start + 1, len(s) + 1):
word = s[start:end]
if word in wordDict:
for sub_sentence in backtrack(end):
if sub_sentence:
res.append(word + ' ' + sub_sentence)
else:
res.append(word)
memo[start] = res
return res
memo = {}
return backtrack(0)
# Example Usage
s = "catsanddog"
wordDict = {"cat", "cats", "and", "sand", "dog"}
print(wordBreak(s, wordDict))var wordBreak = function(s, wordDict) {
const memo = {};
function backtrack(start) {
if (start in memo) return memo[start];
const res = [];
if (start === s.length) return [''];
for (let end = start + 1; end <= s.length; end++) {
const word = s.substring(start, end);
if (wordDict.has(word)) {
const subsentences = backtrack(end);
for (const subsentence of subsentences) {
res.push(subsentence.length ? word + ' ' + subsentence : word);
}
}
}
memo[start] = res;
return res;
}
return backtrack(0);
};
// Example Usage
const s = "catsanddog";
const wordDict = new Set(["cat", "cats", "and", "sand", "dog"]);
console.log(wordBreak(s, wordDict));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
// Define a linked list for storing the results
typedef struct ListNode {
char* val;
struct ListNode* next;
} ListNode;
typedef struct {
ListNode** data;
char** words;
int size;
} Memo;
Memo* initMemo(int size) {
Memo* memo = malloc(sizeof(Memo));
memo->data = malloc(sizeof(ListNode*) * size);
memset(memo->data, 0, sizeof(ListNode*) * size);
memo->words = malloc(sizeof(char*) * size);
for (int i = 0; i < size; i++) {
memo->words[i] = NULL;
}
memo->size = size;
return memo;
}
void freeMemo(Memo* memo) {
for (int i = 0; i < memo->size; i++) {
ListNode* node = memo->data[i];
while (node) {
ListNode* temp = node;
node = node->next;
free(temp->val);
free(temp);
}
}
free(memo->data);
free(memo->words);
free(memo);
}
ListNode* appendString(ListNode* list, const char* word) {
ListNode* newNode = malloc(sizeof(ListNode));
newNode->val = strdup(word);
newNode->next = list;
return newNode;
}
bool findWord(const char* word, char** wordDict, int wordCount) {
for (int i = 0; i < wordCount; ++i) {
if (strcmp(word, wordDict[i]) == 0) {
return true;
}
}
return false;
}
ListNode* backtrack(const char* s, int start, char** wordDict, int wordCount, Memo* memo) {
if (memo->data[start] != NULL) return memo->data[start];
if (start == strlen(s)) {
return appendString(NULL, "");
}
ListNode* result = NULL;
for (int end = start + 1; end <= strlen(s); ++end) {
char* subString = strndup(s + start, end - start);
if (findWord(subString, wordDict, wordCount)) {
ListNode* subList = backtrack(s, end, wordDict, wordCount, memo);
for (ListNode* node = subList; node != NULL; node = node->next) {
char* sentence = node->val[0] ? malloc(strlen(subString) + 1 + strlen(node->val) + 1) : strdup(subString);
if (node->val[0]) sprintf(sentence, "%s %s", subString, node->val);
result = appendString(result, sentence);
free(sentence);
}
}
free(subString);
}
memo->data[start] = result;
return result;
}
char** wordBreak(char* s, char** wordDict, int wordCount, int* returnSize) {
Memo* memo = initMemo(strlen(s) + 1);
ListNode* list = backtrack(s, 0, wordDict, wordCount, memo);
// Calculate returnSize and prepare return array
ListNode* temp = list;
*returnSize = 0;
while (temp) {
(*returnSize)++;
temp = temp->next;
}
char** result = malloc(sizeof(char*) * (*returnSize));
temp = list;
for (int i = 0; i < *returnSize; ++i) {
result[i] = strdup(temp->val);
temp = temp->next;
}
freeMemo(memo);
return result;
}
#include <stdbool.h>
// Example Usage
int main() {
char* s = "catsanddog";
char* wordDict[] = { "cat", "cats", "and", "sand", "dog" };
int wordCount = 5;
int returnSize = 0;
char** sentences = wordBreak(s, wordDict, wordCount, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%s\n", sentences[i]);
free(sentences[i]);
}
free(sentences);
return 0;
}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.
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.
Approach 2: Dynamic Programming
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.
import java.util.*;
public class WordBreak {
public static List<String> wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
List<List<String>> dp = new ArrayList<>(Collections.nCopies(s.length() + 1, null));
dp.set(0, new ArrayList<>(Arrays.asList("")));
for (int i = 1; i <= s.length(); i++) {
List<String> list = new ArrayList<>();
for (int j = 0; j < i; j++) {
if (dp.get(j) != null && wordSet.contains(s.substring(j, i))) {
for (String l : dp.get(j)) {
list.add(l.isEmpty() ? s.substring(j, i) : l + " " + s.substring(j, i));
}
}
}
dp.set(i, list);
}
return dp.get(s.length());
}
// Example Usage
public static void main(String[] args) {
String s = "catsanddog";
List<String> wordDict = Arrays.asList("cat", "cats", "and", "sand", "dog");
System.out.println(wordBreak(s, wordDict));
}
}#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<vector<string>> dp(s.size() + 1);
dp[0].push_back("");
for (int i = 1; i <= s.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (!dp[j].empty() && wordSet.count(s.substr(j, i - j))) {
for (const string& str : dp[j]) {
dp[i].push_back(str + (str.empty() ? "" : " ") + s.substr(j, i - j));
}
}
}
}
return dp[s.size()];
}
};
// Example Usage
int main() {
string s = "catsanddog";
vector<string> wordDict = {"cat", "cats", "and", "sand", "dog"};
Solution solution;
vector<string> result = solution.wordBreak(s, wordDict);
for (const string& sentence : result) {
cout << sentence << endl;
}
return 0;
}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.
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.
Approach 3: Default Approach
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Node
{
public int Index1 { get; set; }
public int Index2 { get; set; }
}
public class Solution {
public IList<string> WordBreak(string s, IList<string> wordDict) {
var paths = new List<Tuple<int, string>>[s.Length + 1];
paths[s.Length] = new List<Tuple<int, string>> { Tuple.Create(-1, (string)null) };
var wordDictGroup = wordDict.GroupBy(word => word.Length);
for (var i = s.Length - 1; i >= 0; --i)
{
paths[i] = new List<Tuple<int, string>>();
foreach (var wordGroup in wordDictGroup)
{
var wordLength = wordGroup.Key;
if (i + wordLength <= s.Length && paths[i + wordLength].Count > 0)
{
foreach (var word in wordGroup)
{
if (s.Substring(i, wordLength) == word)
{
paths[i].Add(Tuple.Create(i + wordLength, word));
}
}
}
}
}
return GenerateResults(paths);
}
private IList<string> GenerateResults(List<Tuple<int, string>>[] paths)
{
var results = new List<string>();
var sb = new StringBuilder();
var stack = new Stack<Node>();
stack.Push(new Node());
while (stack.Count > 0)
{
var node = stack.Peek();
if (node.Index1 == paths.Length - 1 || node.Index2 == paths[node.Index1].Count)
{
if (node.Index1 == paths.Length - 1)
{
results.Add(sb.ToString());
}
stack.Pop();
if (stack.Count > 0)
{
var parent = stack.Peek();
var length = paths[parent.Index1][parent.Index2 - 1].Item2.Length;
if (length < sb.Length) ++length;
sb.Remove(sb.Length - length, length);
}
}
else
{
var newNode = new Node { Index1 = paths[node.Index1][node.Index2].Item1, Index2 = 0 };
if (sb.Length != 0)
{
sb.Append(' ');
}
sb.Append(paths[node.Index1][node.Index2].Item2);
stack.Push(newNode);
++node.Index2;
}
}
return results;
}
}type Trie struct {
children [26]*Trie
isEnd bool
}
func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(word string) {
node := this
for _, c := range word {
c -= 'a'
if node.children[c] == nil {
node.children[c] = newTrie()
}
node = node.children[c]
}
node.isEnd = true
}
func (this *Trie) search(word string) bool {
node := this
for _, c := range word {
c -= 'a'
if node.children[c] == nil {
return false
}
node = node.children[c]
}
return node.isEnd
}
func wordBreak(s string, wordDict []string) []string {
trie := newTrie()
for _, w := range wordDict {
trie.insert(w)
}
var dfs func(string) [][]string
dfs = func(s string) [][]string {
res := [][]string{}
if len(s) == 0 {
res = append(res, []string{})
return res
}
for i := 1; i <= len(s); i++ {
if trie.search(s[:i]) {
for _, v := range dfs(s[i:]) {
v = append([]string{s[:i]}, v...)
res = append(res, v)
}
}
}
return res
}
res := dfs(s)
ans := []string{}
for _, v := range res {
ans = append(ans, strings.Join(v, " "))
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking with Memoization | Time Complexity: O(n^3), where n is the length of the input string, due to substring operations and memoization. |
| Dynamic Programming | Time Complexity: O(n^3), because of substring operations and iteration over previous results. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking (Naive) | O(2^n) | O(n) | Conceptual starting point to explore all splits; impractical for large inputs |
| Backtracking with Memoization | O(2^n) | O(n * 2^n) | Preferred interview solution; avoids recomputing suffix results |
| Bottom-Up Dynamic Programming | O(n^2 + total_sentences) | O(n * total_sentences) | Useful when building sentences iteratively or avoiding recursion depth limits |
Frequently asked questions
Is Word Break II easy or hard?
Word Break II is classified as a Hard problem because it combines recursion, dynamic programming, and combinatorial output generation. The challenge comes from efficiently generating all valid sentences while preventing exponential recomputation of overlapping subproblems.
How to solve Word Break II in O(n)?
An O(n) solution does not exist for Word Break II because the output itself can be exponential in size. Even the optimal algorithms must generate every valid sentence. Practical solutions use backtracking with memoization or dynamic programming to reduce redundant computations while accepting exponential output growth.
What is the best approach for Word Break II?
Backtracking with memoization is the most widely used solution. The algorithm recursively explores valid prefixes and caches results for each starting index to avoid recomputing suffix sentences. This dramatically reduces repeated work compared to naive recursion. Time complexity is still exponential in the worst case because all valid sentences must be generated.
Is Word Break II asked at Google/Amazon/Meta?
Word Break variations appear frequently in interviews at companies like Amazon, Google, and Meta. The easier version (Word Break I) tests dynamic programming fundamentals, while Word Break II evaluates recursion, backtracking, and memoization skills. Candidates are usually expected to discuss pruning repeated subproblems.
What data structure is used in Word Break II?
A hash set is typically used to store dictionary words for O(1) lookups when checking substrings. The recursive solution also uses memoization via a hash map keyed by string index. Some optimized implementations use a Trie to speed up prefix checks while exploring splits.
What is the time complexity of Word Break II?
The worst-case time complexity is O(2^n) because the algorithm may generate an exponential number of valid sentence combinations. Memoization ensures each substring is processed once, but the output size itself can be exponential. Space complexity is also large because all valid sentences must be stored.
Word Break II Python or Java solution approach?
Python implementations commonly use DFS with memoization and a dictionary set for quick lookups. Java solutions often use the same recursive approach with a HashMap cache or a bottom-up dynamic programming list of sentences. Both strategies focus on avoiding repeated computation of the same substring.