Definition
- Word Break – determine if a string can be split into a sequence of one or more dictionary words.
- 1D DP –
dp[i]means the prefix of length i is segmentable;dp[0] = truefor the empty prefix. - Transition –
dp[i] = trueif there exists a j < i wheredp[j]is true andsubstring(j, i)is in the dictionary. - Dictionary as HashSet – O(1) average-case lookup for each candidate word.
- Complexity – O(n^2 * L) time, O(n) space for the DP array.
At National Bank of India, a legacy channel sends payment instructions as one concatenated string with no separators. Rajesh's parser must verify a clean split into known command words. A position is reachable if an earlier reachable position is followed by a valid word ending here.
Understanding the Concepts
What is the Word Break problem?
Given a string and a dictionary of words, determine whether the string can be segmented into a space-separated sequence of one or more dictionary words. For example, "leetcode" with dictionary ["leet", "code"] is segmentable as "leet code".
package com.bank.core;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class WordBreak {
public static boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
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 static void main(String[] args) {
System.out.println(wordBreak("leetcode", List.of("leet", "code"))); // true
System.out.println(wordBreak("catsandog", List.of("cats", "dog", "sand", "and", "cat"))); // false
}
}
true
false
Why does a greedy approach fail?
A greedy approach that always takes the longest (or shortest) matching word can fail. Consider "catsand" with dictionary ["cat", "cats", "and", "sand"]. Greedy longest-first picks "cats" leaving "and" which works. But change the string to "catsandog": greedy picks "cats" leaving "andog" where no valid split exists. The DP explores all breakpoints.
package com.bank.core;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class GreedyFails {
public static boolean wordBreak(String s, List<String> dict) {
Set<String> set = new HashSet<>(dict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++)
for (int j = 0; j < i; j++)
if (dp[j] && set.contains(s.substring(j, i))) { dp[i] = true; break; }
return dp[s.length()];
}
public static void main(String[] args) {
// Greedy longest-first would pick "cats" + "and" but miss that "cat" + "sand" also works
System.out.println(wordBreak("catsand", List.of("cat", "cats", "and", "sand"))); // true
}
}
true
How does the DP transition work?
The DP array has size n+1. dp[0] = true because the empty prefix is trivially segmentable. For each end position i from 1 to n, try every start position j from 0 to i-1. If dp[j] is true and the substring from j to i is a dictionary word, then dp[i] is true. The answer is dp[n].
The intuition is that a prefix is segmentable exactly when it ends with a valid word whose starting point is itself a segmentable boundary.
package com.bank.core;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class DPTransitionExplained {
public static void main(String[] args) {
String s = "applepenapple";
Set<String> dict = new HashSet<>(List.of("apple", "pen"));
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;
System.out.println("dp[" + i + "]=true via word '" + s.substring(j, i) + "' from j=" + j);
break;
}
}
}
System.out.println("Result: " + dp[n]);
}
}
dp[5]=true via word 'apple' from j=0
dp[8]=true via word 'pen' from j=5
dp[13]=true via word 'apple' from j=8
Result: true
How can you optimise with max word length?
Instead of trying all j from 0 to i-1, limit j to i - maxWordLength since no dictionary word is longer than maxWordLength. This reduces the inner loop from O(n) to O(maxWordLength).
package com.bank.core;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class WordBreakOptimised {
public static boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
int maxLen = wordDict.stream().mapToInt(String::length).max().orElse(0);
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = Math.max(0, i - maxLen); j < i; j++) {
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
public static void main(String[] args) {
System.out.println(wordBreak("applepenapple", List.of("apple", "pen"))); // true
}
}
true
What are the edge cases?
Edge cases include empty strings, single-character dictionaries, strings that cannot be split at all, and strings where every character is a dictionary word.
package com.bank.core;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class WordBreakEdgeCases {
public static boolean wordBreak(String s, List<String> dict) {
Set<String> set = new HashSet<>(dict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++)
for (int j = 0; j < i; j++)
if (dp[j] && set.contains(s.substring(j, i))) { dp[i] = true; break; }
return dp[s.length()];
}
public static void main(String[] args) {
System.out.println("Empty: " + wordBreak("", List.of("a"))); // true
System.out.println("No split: " + wordBreak("xyz", List.of("a", "b"))); // false
System.out.println("Each char: " + wordBreak("abc", List.of("a", "b", "c"))); // true
}
}
Empty: true
No split: false
Each char: true
What about Word Break II (return all sentences)?
The follow-up Word Break II asks you to return all possible segmentations, not just whether one exists. The output can be exponentially large, so use memoised backtracking rather than simple DP.
package com.bank.core;
import java.util.*;
public class WordBreakII {
public static 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 static 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(""); return result; }
for (int end = start + 1; end <= s.length(); end++) {
String word = s.substring(start, end);
if (dict.contains(word)) {
for (String sub : backtrack(s, end, dict, memo)) {
result.add(word + (sub.isEmpty() ? "" : " " + sub));
}
}
}
memo.put(start, result);
return result;
}
public static void main(String[] args) {
System.out.println(wordBreak("catsanddog", List.of("cat", "cats", "and", "sand", "dog")));
}
}
[cat sand dog, cats and dog]
What is the time and space complexity?
The basic Word Break DP runs in O(n^2) time for the two nested loops, with each iteration costing up to O(L) for substring creation and HashSet lookup, giving O(n^2 * L) total. Space is O(n) for the DP array. The max-word-length optimisation reduces the inner loop to O(maxLen) iterations.
What is the banking use case?
At National Bank of India, a legacy channel sends payment instructions as one concatenated string of command words with no separators. Rajesh's parser uses this DP to verify a clean split before the execution engine processes the commands. A greedy longest-word match could fail because an early wrong cut blocks a valid later split, so Rajesh uses the DP that remembers every reachable boundary.
package com.bank.service;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class PaymentInstructionParser {
private final Set<String> commands;
public PaymentInstructionParser(List<String> validCommands) {
this.commands = new HashSet<>(validCommands);
}
public boolean canParse(String instruction) {
int n = instruction.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] && commands.contains(instruction.substring(j, i))) { dp[i] = true; break; }
return dp[n];
}
public static void main(String[] args) {
PaymentInstructionParser parser = new PaymentInstructionParser(
List.of("transfer", "deposit", "balance", "check")
);
System.out.println(parser.canParse("transferbalancecheck")); // true
System.out.println(parser.canParse("transferbal")); // false
}
}
true
false
Visual Overview
Word Break DP
═════════════
s = "leetcode", dict = {"leet", "code"}
dp: [T] [F] [F] [F] [T] [F] [F] [F] [T]
0 1 2 3 4 5 6 7 8
▲ ▲
"leet" found "code" found
dp[0]=T dp[4]=T
dp[4] = true because dp[0]=true and "leet" in dict
dp[8] = true because dp[4]=true and "code" in dict
Answer: dp[8] = true
Key Takeaway
Word Break is a one-dimensional dynamic programming problem over string positions. Define dp[i] as whether the prefix of length i can be segmented into dictionary words. The base case dp[0] = true means the empty prefix is trivially segmentable. For each position, look back at every earlier position and check if it is a segmentable boundary followed by a dictionary word ending at the current position.
A greedy approach fails because an early wrong cut can block a valid later split. The DP remembers every reachable boundary, so it finds a valid segmentation if one exists. Putting the dictionary into a HashSet gives O(1) lookups, and limiting the inner loop to the max word length is a practical optimisation.
The follow-up Word Break II returns all possible segmentations and needs memoised backtracking because the output can be exponentially large.
In the banking project at National Bank of India, Rajesh's parser verifies that concatenated payment instructions split cleanly into known command words before the execution engine processes them.
Remember one sentence: dp[i] is true if some earlier dp[j] is true and substring(j,i) is a dictionary word, giving O(n^2) segmentation checking.
---