Approach

Word Break II

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 possible sentences in any order.

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

Examples

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.

Approach

Key Insight

This is Word Break I + Backtracking!

At each position, try all words that match current prefix
Recursively solve remaining string
Combine results to form complete sentences
Use memoization to avoid recomputing same substrings

Solution 1: Backtracking with Memoization

Use DFS with memoization to find all valid segmentations.

Algorithm:

Convert wordDict to set for O(1) lookup
Use memo map: substring → list of all valid sentences
At each position:
- Try all possible word matches from current position
- Recursively solve rest of string
- Combine current word with solutions from rest
Base case: empty string → return [""]

Complexity:

Time: O(2^n × n) worst case (all possible partitions)
Space: O(2^n × n) for memoization + recursion stack

Solution 2: Dynamic Programming (Bottom-up)

Build solutions from end to start.

Algorithm:

Create dp array: dp[i] = list of all valid sentences starting at index i
Base case: dp[n] = [""] (empty string at end)
For each position from right to left:
- Try all words that match at current position
- If match found, combine word with dp[i + word.length]
Return dp[0]

Complexity:

Time: O(2^n × n) worst case
Space: O(2^n × n) for DP array

Solution 3: Backtracking with Early Termination

Use Word Break I check first to avoid impossible cases.

Algorithm:

First check if string is breakable using Word Break I DP
If not breakable, return [] immediately
Otherwise, use backtracking with memoization
This optimization helps when no valid segmentation exists

Complexity:

Time: O(n^2 + 2^n × n) - O(n^2) for check, O(2^n × n) for backtracking
Space: O(2^n × n)

Solution 4: Trie-based Backtracking

Build Trie from dictionary for efficient prefix matching.

Algorithm:

Build Trie from wordDict
Use Trie for efficient word matching during backtracking
At each position, traverse Trie to find all matching words
Recursively solve with memoization

Complexity:

Time: O(m + 2^n × n) where m = total characters in wordDict
Space: O(m + 2^n × n) for Trie + memoization

Complexity Analysis

| Approach | Time | Space | |----------|------|-------| | Backtracking + Memo | O(2^n × n) | O(2^n × n) | | DP Bottom-up | O(2^n × n) | O(2^n × n) | | With Early Check | O(n^2 + 2^n × n) | O(2^n × n) | | Trie-based | O(m + 2^n × n) | O(m + 2^n × n) |

Pattern Recognition

This problem demonstrates:

Backtracking to explore all possibilities
Memoization to avoid recomputation
String segmentation pattern
Trie for efficient prefix matching
Extends Word Break I from decision to enumeration
Similar patterns: Palindrome Partitioning II, Concatenated Words

Solution

java

1import java.util.*;
2
3class Solution {
4    // Solution 1: Backtracking with Memoization
5    public List<String> wordBreak(String s, List<String> wordDict) {
6        Set<String> wordSet = new HashSet<>(wordDict);
7        Map<String, List<String>> memo = new HashMap<>();
8        return backtrack(s, wordSet, memo);
9    }
10
11    private List<String> backtrack(String s, Set<String> wordSet, Map<String, List<String>> memo) {
12        // Base case: empty string
13        if (s.isEmpty()) {
14            return Arrays.asList("");
15        }
16
17        // Check memo
18        if (memo.containsKey(s)) {
19            return memo.get(s);
20        }
21
22        List<String> result = new ArrayList<>();
23
24        // Try all possible first words
25        for (int i = 1; i <= s.length(); i++) {
26            String word = s.substring(0, i);
27            if (wordSet.contains(word)) {
28                // Recursively solve rest of string
29                List<String> restSentences = backtrack(s.substring(i), wordSet, memo);
30
31                // Combine current word with sentences from rest
32                for (String sentence : restSentences) {
33                    if (!sentence.isEmpty()) {
34                        result.add(word + " " + sentence);
35                    } else {
36                        result.add(word);
37                    }
38                }
39            }
40        }
41
42        memo.put(s, result);
43        return result;
44    }
45
46    // Solution 2: Dynamic Programming (Bottom-up)
47    public List<String> wordBreakDP(String s, List<String> wordDict) {
48        Set<String> wordSet = new HashSet<>(wordDict);
49        int n = s.length();
50
51        // dp[i] = list of all valid sentences starting at index i
52        List<List<String>> dp = new ArrayList<>();
53        for (int i = 0; i <= n; i++) {
54            dp.add(new ArrayList<>());
55        }
56        dp.get(n).add("");  // Base case: empty string
57
58        // Build from right to left
59        for (int i = n - 1; i >= 0; i--) {
60            for (int j = i + 1; j <= n; j++) {
61                String word = s.substring(i, j);
62                if (wordSet.contains(word)) {
63                    // Combine word with sentences from dp[j]
64                    for (String sentence : dp.get(j)) {
65                        if (!sentence.isEmpty()) {
66                            dp.get(i).add(word + " " + sentence);
67                        } else {
68                            dp.get(i).add(word);
69                        }
70                    }
71                }
72            }
73        }
74
75        return dp.get(0);
76    }
77
78    // Solution 3: Backtracking with Early Termination
79    public List<String> wordBreakOptimized(String s, List<String> wordDict) {
80        Set<String> wordSet = new HashSet<>(wordDict);
81
82        // First check if string is breakable (Word Break I)
83        if (!canBreak(s, wordSet)) {
84            return new ArrayList<>();
85        }
86
87        // Now do backtracking
88        Map<String, List<String>> memo = new HashMap<>();
89        return backtrack(s, wordSet, memo);
90    }
91
92    private boolean canBreak(String s, Set<String> wordSet) {
93        int n = s.length();
94        boolean[] dp = new boolean[n + 1];
95        dp[0] = true;
96
97        for (int i = 1; i <= n; i++) {
98            for (int j = 0; j < i; j++) {
99                if (dp[j] && wordSet.contains(s.substring(j, i))) {
100                    dp[i] = true;
101                    break;
102                }
103            }
104        }
105
106        return dp[n];
107    }
108
109    // Solution 4: Trie-based Backtracking
110    public List<String> wordBreakTrie(String s, List<String> wordDict) {
111        // Build Trie
112        TrieNode root = new TrieNode();
113        for (String word : wordDict) {
114            TrieNode node = root;
115            for (char c : word.toCharArray()) {
116                if (!node.children.containsKey(c)) {
117                    node.children.put(c, new TrieNode());
118                }
119                node = node.children.get(c);
120            }
121            node.isWord = true;
122        }
123
124        Map<Integer, List<String>> memo = new HashMap<>();
125        return backtrackTrie(s, 0, root, memo);
126    }
127
128    private List<String> backtrackTrie(String s, int start, TrieNode root, Map<Integer, List<String>> memo) {
129        // Base case: reached end
130        if (start == s.length()) {
131            return Arrays.asList("");
132        }
133
134        // Check memo
135        if (memo.containsKey(start)) {
136            return memo.get(start);
137        }
138
139        List<String> result = new ArrayList<>();
140        TrieNode node = root;
141
142        // Try all words starting at current position
143        for (int i = start; i < s.length(); i++) {
144            char c = s.charAt(i);
145            if (!node.children.containsKey(c)) {
146                break;
147            }
148            node = node.children.get(c);
149
150            // Found a complete word
151            if (node.isWord) {
152                String word = s.substring(start, i + 1);
153                List<String> restSentences = backtrackTrie(s, i + 1, root, memo);
154
155                for (String sentence : restSentences) {
156                    if (!sentence.isEmpty()) {
157                        result.add(word + " " + sentence);
158                    } else {
159                        result.add(word);
160                    }
161                }
162            }
163        }
164
165        memo.put(start, result);
166        return result;
167    }
168
169    // Helper class for Trie
170    class TrieNode {
171        Map<Character, TrieNode> children = new HashMap<>();
172        boolean isWord = false;
173    }
174}
175