Java - Word Break Problem
Problem Statement
Given a string s and a dictionary of words wordDict, determine if s can be segmented into a sequence of one or more dictionary words.
Example 1
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: "leetcode" can be segmented as "leet code".
Example 2
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: "applepenapple" can be segmented as "apple pen apple".
Example 3
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Explanation: "catsandog" cannot be segmented into words from the dictionary.
Approach 1: Dynamic Programming (Bottom-Up)
Use a boolean DP array (dp[i]) where dp[i] = true means the substring s[0...i] can be segmented.
Iterate over s and check all possible prefixes that exist in wordDict.
If dp[j] is true and s[j...i] exists in wordDict, set dp[i] = true.
import java.util.*;
public class WordBreak {
public static boolean wordBreak(String s, List wordDict) {
Set wordSet = new HashSet<>(wordDict); // Convert list to set for O(1) lookup
int n = s.length();
boolean[] dp = new boolean[n + 1]; // DP array
dp[0] = true; // Empty string is always valid
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordSet.contains(s.substring(j, i))) {
dp[i] = true;
break; // No need to check further if we found a valid partition
}
}
}
return dp[n]; // Final result
}
public static void main(String[] args) {
String s = "leetcode";
List wordDict = Arrays.asList("leet", "code");
System.out.println("Can the word be segmented? " + wordBreak(s, wordDict)); // true
}
}
Approach 2: Recursion + Memoization (Top-Down)
Try to break the string recursively at every possible prefix.
Use memoization (Map<Integer, Boolean> memo) to avoid recomputation.
If any valid partition is found, return true.
import java.util.*;
public class WordBreakRecursive {
private static Map<Integer, Boolean> memo = new HashMap<>();
public static boolean wordBreak(String s, List wordDict) {
Set wordSet = new HashSet<>(wordDict);
return helper(s, wordSet, 0);
}
private static boolean helper(String s, Set wordSet, int start) {
if (start == s.length()) return true; // Successfully segmented
if (memo.containsKey(start)) return memo.get(start); // Return memoized result
for (int end = start + 1; end <= s.length(); end++) {
if (wordSet.contains(s.substring(start, end)) && helper(s, wordSet, end)) {
memo.put(start, true);
return true;
}
}
memo.put(start, false);
return false;
}
public static void main(String[] args) {
String s = "applepenapple";
List wordDict = Arrays.asList("apple", "pen");
System.out.println("Can the word be segmented? " + wordBreak(s, wordDict)); // true
}
}
Complexity Analysis
Approach Time Complexity Space Complexity
DP (Bottom-Up) O(N^2) O(N)
Recursion + Memoization O(N^2) O(N)
Dynamic Programming is the most efficient and recommended approach.
Recursion is useful for understanding the problem but may cause a stack overflow for large inputs.
Extensions: Printing All Possible Segmentations
Instead of returning true/false, we can print all possible segmentations of the word.
import java.util.*;
public class WordBreakAll {
public static List wordBreak(String s, List wordDict) {
Set wordSet = new HashSet<>(wordDict);
List result = new ArrayList<>();
backtrack(s, wordSet, 0, "", result);
return result;
}
private static void backtrack(String s, Set wordSet, int start, String current, List result) {
if (start == s.length()) {
result.add(current.trim()); // Remove leading space
return;
}
for (int end = start + 1; end <= s.length(); end++) {
String prefix = s.substring(start, end);
if (wordSet.contains(prefix)) {
backtrack(s, wordSet, end, current + " " + prefix, result);
}
}
}
public static void main(String[] args) {
String s = "catsanddog";
List wordDict = Arrays.asList("cat", "cats", "and", "sand", "dog");
System.out.println("Possible Segmentations: " + wordBreak(s, wordDict));
// Output: ["cat sand dog", "cats and dog"]
}
}
