Skip to main content
Talentd

Word Break II - Solution & Explanation

HardArrayHash TableStringDynamic Programming12 min readAsked at: Amazon, Microsoft, Meta +13
Practice this problem

Problem Statement

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 <= 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.
  • 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.

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.

Code

PythonJavaScriptC

Python

JavaScript

C

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaC++

Java

C++

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaGoC#

Python

Java

Go

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking with Memoization

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.

Dynamic Programming

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking (Naive)O(2^n)O(n)Conceptual starting point to explore all splits; impractical for large inputs
Backtracking with MemoizationO(2^n)O(n * 2^n)Preferred interview solution; avoids recomputing suffix results
Bottom-Up Dynamic ProgrammingO(n^2 + total_sentences)O(n * total_sentences)Useful when building sentences iteratively or avoiding recursion depth limits

Video Solution

Word Break 2 | Leetcode #140 • Techdose • 35,703 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Word Break II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Concatenated Words

Next

Word Break