Word Break II

Problem Description

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.

The same word in the dictionary may be reused multiple times in the segmentation.

Examples

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 in wordDict are unique

Two-Phase: Prune with DP, Then Backtrack

Jumping straight to backtracking on an unsolvable input means exploring a huge space just to find nothing. First check if any segmentation is possible using the Word Break I DP approach. If dp[s.length()] = false, return immediately.

For the backtracking: at each position, try every prefix of the remaining string that appears in the dictionary. If it matches, recurse on the suffix. Build words forward and collect complete sentences at the end of the string.

Memoizing the backtrack results by starting index prevents re-exploring the same suffix multiple times when multiple prefixes lead to the same position.

Solution: Backtracking with Memoization

import java.util.*;

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 backtrack(s, 0, dict, memo);
    }

    private List<String> backtrack(String s, int start,
                                     Set<String> dict, Map<Integer, List<String>> memo) {
        if (memo.containsKey(start)) return memo.get(start);

        List<String> result = new ArrayList<>();
        if (start == s.length()) {
            result.add(""); // base case: empty suffix forms a valid ending
            return result;
        }

        for (int end = start + 1; end <= s.length(); end++) {
            String word = s.substring(start, end);
            if (dict.contains(word)) {
                List<String> suffixes = backtrack(s, end, dict, memo);
                for (String suffix : suffixes) {
                    result.add(word + (suffix.isEmpty() ? "" : " " + suffix));
                }
            }
        }

        memo.put(start, result);
        return result;
    }
}

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> list[str]:
        word_set = set(wordDict)
        memo = {}

        def backtrack(start: int) -> list[str]:
            if start in memo:
                return memo[start]

            if start == len(s):
                return [""]  # base: empty suffix is valid

            result = []
            for end in range(start + 1, len(s) + 1):
                word = s[start:end]
                if word in word_set:
                    for suffix in backtrack(end):
                        result.append(word + ("" if not suffix else " " + suffix))

            memo[start] = result
            return result

        return backtrack(0)

#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>

class Solution {
public:
    std::vector<std::string> wordBreak(std::string s, std::vector<std::string>& wordDict) {
        std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());
        std::unordered_map<int, std::vector<std::string>> memo;
        return backtrack(s, 0, dict, memo);
    }

private:
    std::vector<std::string> backtrack(
            const std::string& s, int start,
            std::unordered_set<std::string>& dict,
            std::unordered_map<int, std::vector<std::string>>& memo) {
        if (memo.count(start)) return memo[start];

        std::vector<std::string> result;
        if (start == (int)s.size()) {
            result.push_back("");
            return result;
        }

        for (int end = start + 1; end <= (int)s.size(); end++) {
            std::string word = s.substr(start, end - start);
            if (dict.count(word)) {
                for (const std::string& suffix : backtrack(s, end, dict, memo)) {
                    result.push_back(word + (suffix.empty() ? "" : " " + suffix));
                }
            }
        }

        memo[start] = result;
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n^3 + 2^n * n). Substring extraction is O(n) per end position, and there can be exponentially many sentences in the worst case (e.g., s = "aaaa..." and dict contains "a", "aa", etc.).
• Space Complexity: O(2^n * n) to store all sentences in the memoization table.

Where it breaks: the memoization helps when many prefixes lead to the same suffix position. It does not help when the output itself is exponentially large, because you still have to build and return all the sentences. For an input designed to produce the maximum number of sentences, no approach avoids O(2^n) output.

Common Mistakes

• Returning [""] at the base case instead of []. An empty list at the base would mean no sentence gets built. The empty string "" acts as a valid terminal that allows the caller to append the last word cleanly.
• Constructing sentences in reverse (suffix first) without reversing at the end. Building forward (prefix first) avoids this issue entirely.
• Not using a set for the dictionary. Looking up each word in a list is O(dict.length) per check. Use a hash set for O(1) lookup.

Frequently Asked Questions

How does Word Break II differ from Word Break I? Word Break I asks if segmentation is possible (boolean). Word Break II asks for all valid segmentations (list of strings). The DP approach from I doesn’t extend to II because you need to enumerate paths, not just check existence.

When does memoization help the most? When many different prefixes lead to the same suffix starting position. For example, if s = "catcat" and dict contains "cat" and "ca" and "t", two different splits of the prefix both reach position 3. Without memoization, you’d explore the same suffix twice.

← All Problems