BackTrackingProblem 3 of 19
Word Break Problem using Backtracking
Problem Statement
Given a string and a dictionary of words, determine if the string can be segmented into a space-separated sequence of one or more dictionary words. Print all possible ways to break the string.
Example:
Input:
s = "catsanddog"
dictionary = ["cat", "cats", "and", "sand", "dog"]
Output:
["cats and dog", "cat sand dog"]
Explanation:
"catsanddog" can be segmented as:
- "cats" + "and" + "dog"
- "cat" + "sand" + "dog"
Approach 1: Brute Force (Pure Backtracking)
Intuition
Try every possible prefix of the string. If the prefix exists in the dictionary, recursively try to break the remaining suffix. This explores all possible segmentations.
Algorithm
- Start from index 0
- Try all prefixes ending at positions 1 to n
- If prefix is in dictionary, add it to current path and recurse on suffix
- If end of string reached, store the current segmentation
- Backtrack and try longer prefixes
java
import java.util.*;
class Solution {
public void backtrack(String s, int start, Set<String> dict,
List<String> current, List<String> result) {
// Base case: reached end of string
if (start == s.length()) {
result.add(String.join(" ", current));
return;
}
// Try all possible prefixes
for (int end = start + 1; end <= s.length(); end++) {
String prefix = s.substring(start, end);
if (dict.contains(prefix)) {
current.add(prefix);
backtrack(s, end, dict, current, result);
current.remove(current.size() - 1); // Backtrack
}
}
}
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
List<String> result = new ArrayList<>();
List<String> current = new ArrayList<>();
backtrack(s, 0, dict, current, result);
return result;
}
}Complexity Analysis
- Time Complexity: O(2^n) - In worst case, every partition is valid
- Space Complexity: O(n) - Recursion stack depth
Approach 2: Optimal (Backtracking with Memoization)
Intuition
Use memoization to avoid recomputing results for the same suffix. Store all valid segmentations starting from each index to avoid redundant work.
Algorithm
- Use a map to store computed results for each starting index
- Before computing, check if result already exists
- If not, compute and store the result
- Combine stored results with current word choices
java
import java.util.*;
class Solution {
private Map<Integer, List<String>> memo = new HashMap<>();
public List<String> backtrack(String s, int start, Set<String> dict) {
// Check memo
if (memo.containsKey(start)) {
return memo.get(start);
}
List<String> result = new ArrayList<>();
// Base case: reached end of string
if (start == s.length()) {
result.add("");
return result;
}
// Try all possible prefixes
for (int end = start + 1; end <= s.length(); end++) {
String prefix = s.substring(start, end);
if (dict.contains(prefix)) {
List<String> suffixWays = backtrack(s, end, dict);
for (String suffix : suffixWays) {
if (suffix.isEmpty()) {
result.add(prefix);
} else {
result.add(prefix + " " + suffix);
}
}
}
}
memo.put(start, result);
return result;
}
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
memo.clear();
return backtrack(s, 0, dict);
}
}Complexity Analysis
- Time Complexity: O(n² × m) - n positions, n prefixes each, m = number of valid sentences
- Space Complexity: O(n × m) - Memoization storage
Approach 3: DP Check + Backtracking
Intuition
First use DP to check if the string can be segmented at all. Then only if segmentation is possible, use backtracking to find all solutions. This avoids unnecessary backtracking when no solution exists.
java
import java.util.*;
class Solution {
public boolean canBreak(String s, Set<String> dict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
public void backtrack(String s, int start, Set<String> dict,
List<String> current, List<String> result) {
if (start == s.length()) {
result.add(String.join(" ", current));
return;
}
for (int end = start + 1; end <= s.length(); end++) {
String prefix = s.substring(start, end);
if (dict.contains(prefix)) {
current.add(prefix);
backtrack(s, end, dict, current, result);
current.remove(current.size() - 1);
}
}
}
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
List<String> result = new ArrayList<>();
if (!canBreak(s, dict)) return result;
backtrack(s, 0, dict, new ArrayList<>(), result);
return result;
}
}Complexity Analysis
- Time Complexity: O(n² + 2^n) - O(n²) for DP check, O(2^n) for backtracking
- Space Complexity: O(n) - For DP array and recursion stack
Key Takeaways
- HashSet for Dictionary: O(1) lookup vs O(m) for list search
- Memoization: Avoid recomputing the same suffix segmentations
- DP Pre-check: Can save time by checking feasibility first
- LeetCode #140: Word Break II - Classic backtracking with memoization
- Prefix Iteration: Try all prefixes, not just dictionary word lengths
- String Building: Be careful with space handling when joining words