Log inSign up
hardleetcodeNot Started

Word Break II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

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"]
Explanation: Both segmentations are valid sentences containing only dictionary words.

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 dictionary words.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []
Explanation: No valid sentence segmentation exists.

Constraints:

  • 1 <= s.length <= 20
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 10
  • s and wordDict[i] consist of lowercase English letters.
  • All the strings of wordDict are unique.
  • Input is generated such that the total number of sentences does not exceed 105.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Construct all valid sentence paths using suffix memoization.
  • Prepend matching prefixes to sub-sentence lists.
  • Differentiate decision DP (Word Break I) from construction backtracking (Word Break II).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Constructing all valid space-separated sentences matching dictionary words.
  • All-paths enumeration on a directed acyclic segmentation graph.

Algorithmic Decision Tree:

  • Constructing all valid space-separated sentences matching dictionary words.
  • All-paths enumeration on a directed acyclic segmentation graph.

Connected Patterns:

Word BreakPalindrome PartitioningConcatenated Words

1. Pure Recursive Backtracking without Cache

Intuition

Maintain current path of chosen words. If start == s.length, join path with spaces and add to results. For end from start + 1 to s.length: if s[start...end-1] in dictionary, push word to path, recurse on end, and pop word upon backtracking.

When to apply: Basic baseline comparison.

Algorithm

  1. Initialize res = [] and path = [].
  2. Helper backtrack(start):
  3. If start == s.length: res.push(path.join(' ')); return.
  4. For end from start + 1 to s.length:
  5. w = s.substr(start, end - start).
  6. If dict.contains(w):
  7. path.push(w).
  8. backtrack(end).
  9. path.pop().
  10. Return res.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_set>
5
6class Solution {
7 void backtrack(int start, const std::string& s, const std::unordered_set<std::string>& dict, std::vector<std::string>& current, std::vector<std::string>& res) {
8 if (start == (int)s.size()) {
9 std::string sentence = "";
10 for (int i = 0; i < (int)current.size(); ++i) {
11 if (i > 0) sentence += " ";
12 sentence += current[i];
13 }
14 res.push_back(sentence);
15 return;
16 }
17
18 for (int end = start + 1; end <= (int)s.size(); ++end) {
19 std::string word = s.substr(start, end - start);
20 if (dict.count(word)) {
21 current.push_back(word);
22 backtrack(end, s, dict, current, res);
23 current.pop_back();
24 }
25 }
26 }
27public:
28 std::vector<std::string> wordBreak(std::string s, std::vector<std::string>& wordDict) {
29 std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());
30 std::vector<std::string> res, current;
31 backtrack(0, s, dict, current, res);
32 return res;
33 }
34};
35
36int main() {
37 Solution sol;
38 std::vector<std::string> dict = {"cat","cats","and","sand","dog"};
39 auto ans = sol.wordBreak("catsanddog", dict);
40 for (const auto& sent : ans) std::cout << sent << std::endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(2^N * N) — In the worst case where all prefixes are valid, generates 2N paths of length N.
  • Space complexity: O(N) call stack

Why Brute Force Doesn't Scale:

Memoizing suffix sentences guarantees each suffix is parsed at most once.

Only stores reachable, successful sub-sentence lists.

2. Bottom-Up DP with Sentence List Table

Intuition

Initialize dp[0] = [""]. For i from 1 to N: for j from 0 to i - 1: if dp[j] is non-empty and word = s[j...i-1] is in wordDict, for each sentence in dp[j], append sentence + (sentence.empty ? "" : " ") + word into dp[i]. Return dp[N].

When to apply: When non-recursive bottom-up reconstruction is preferred.

Algorithm

  1. dp = Array(n + 1).fill([]).
  2. dp[0] = [""].
  3. For i from 1 to n:
  4. For j from 0 to i - 1:
  5. w = s.substr(j, i - j).
  6. If dict.contains(w) && dp[j].length > 0:
  7. For sent in dp[j]:
  8. dp[i].push(sent ? sent + ' ' + w : w).
  9. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_set>
5
6class Solution {
7public:
8 std::vector<std::string> wordBreak(std::string s, std::vector<std::string>& wordDict) {
9 std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());
10 int n = s.size();
11 std::vector<std::vector<std::string>> dp(n + 1);
12 dp[0] = {""};
13
14 for (int i = 1; i <= n; ++i) {
15 for (int j = 0; j < i; ++j) {
16 std::string word = s.substr(j, i - j);
17 if (dict.count(word) && !dp[j].empty()) {
18 for (const auto& prev : dp[j]) {
19 dp[i].push_back(prev.empty() ? word : prev + " " + word);
20 }
21 }
22 }
23 }
24 return dp[n];
25 }
26};
27
28int main() {
29 Solution sol;
30 std::vector<std::string> dict = {"cat","cats","and","sand","dog"};
31 auto ans = sol.wordBreak("catsanddog", dict);
32 for (const auto& sent : ans) std::cout << sent << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(2^N + totalOutputLen) — Builds partial sentence lists bottom-up for each prefix length.
  • Space complexity: O(2^N * N)

3. DFS with Suffix Memoization (Optimal)

Intuition

Define dfs(start) returning a list of all valid segmented sentences from s[start...]. Base case: start == s.length returns [""]. If start is in memo, return memo[start]. Iterate end from start + 1 to s.length: if word = s[start...end-1] is in wordDict, recursively call dfs(end). For each sub-sentence returned, append word + (sub.empty ? "" : " " + sub) to the result list for start. Cache in memo[start] and return.

When to apply: The standard gold standard solution for Word Break II.

Algorithm

  1. Initialize memo hash map.
  2. Helper dfs(start):
  3. If start == s.length: return [""].
  4. If memo.count(start): return memo[start].
  5. res = [].
  6. For end from start + 1 to s.length:
  7. w = s.substr(start, end - start).
  8. If dict.contains(w):
  9. subSentences = dfs(end).
  10. For sub in subSentences:
  11. res.push(sub.empty ? w : w + ' ' + sub).
  12. Store memo[start] = res.
  13. Return res.
  14. Return dfs(0).

DFS Memoization Graph Path Construction

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [c, a, t, s, a, n, d, d, o, g]
Current operationSTEP 1 OF 6
Observation: Match string "catsanddog" from start: prefixes "cat" (len 3) and "cats" (len 4) both exist in wordDict
Visual state
Values and pointers at this exact step
array
S
cat
cats
and
sand
dog
0
↑ Prefix candidates for "catsanddog"
1
2
3
4
Variables at this step
string
catsanddog
validPrefixes
["cat","cats"]
Why this step matters

Observation: Match string "catsanddog" from start: prefixes "cat" (len 3) and "cats" (len 4) both exist in wordDict.

Decision: Fork DFS into two exploration branches: Branch 1 ("cat" + remainder "sanddog") and Branch 2 ("cats" + remainder "anddog").

Invariant: All valid segmentations start with a dictionary prefix.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_set>
5#include <unordered_map>
6
7class Solution {
8 std::unordered_map<int, std::vector<std::string>> memo;
9
10 std::vector<std::string> dfs(int start, const std::string& s, const std::unordered_set<std::string>& dict) {
11 if (start == (int)s.size()) return {""};
12 if (memo.count(start)) return memo[start];
13
14 std::vector<std::string> res;
15 for (int end = start + 1; end <= (int)s.size(); ++end) {
16 std::string word = s.substr(start, end - start);
17 if (dict.count(word)) {
18 auto subSentences = dfs(end, s, dict);
19 for (const auto& sub : subSentences) {
20 res.push_back(sub.empty() ? word : word + " " + sub);
21 }
22 }
23 }
24 return memo[start] = res;
25 }
26public:
27 std::vector<std::string> wordBreak(std::string s, std::vector<std::string>& wordDict) {
28 std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());
29 memo.clear();
30 return dfs(0, s, dict);
31 }
32};
33
34int main() {
35 Solution sol;
36 std::vector<std::string> dict = {"cat","cats","and","sand","dog"};
37 auto ans = sol.wordBreak("catsanddog", dict);
38 for (const auto& sent : ans) std::cout << sent << std::endl;
39 // Output:
40 // cat sand dog
41 // cats and dog
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(2^N + totalOutputLen) — Suffix caching prevents re-evaluating identical suffixes across different prefix combinations.
  • Space complexity: O(2^N * N) for memoization table

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Naive Backtracking (No Memoization)O(2^N * N)O(N) recursion stackSimple recursive search.Exponential recomputation on repeated suffixes.
2.DFS with Suffix Memoization (Optimal)OptimalO(2^N + totalOutputLen)O(2^N * N) memoization cacheCaches sentences for each suffix, pruning duplicate branch exploration.Higher memory usage for storing cached string lists.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not memoizing suffix results, causing exponential TLE on strings with numerous overlapping word combinations.

Pitfall 2:

Trailing or leading spaces introduced during string joins.

Crucial Edge Cases to Validate:

  • No valid segmentation (s = catsandog): Returns [] without adding any invalid sentences.
  • Entire string is a single dictionary word (s = apple, wordDict = [apple]): Returns [apple].
  • Multiple overlapping words: Memoization caches all sub-combinations cleanly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the contrast between Word Break I (decision problem, O(N2)) and Word Break II (generation problem, O(2N)).
  2. Show how suffix memoization reuses completed sub-sentence branches.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does memoizing dfs(start) return an array of strings rather than a boolean?

Back to DSA Sheet