Word Break — BFS Over Split Positions
Treat indices as graph nodes and BFS through valid dictionary cuts to decide whether the entire string can be segmented.
Problem Statement
Given a string s and a dictionary of words, determine if s can be segmented into a space-separated sequence of dictionary words.
Why This Problem Matters
- Introduces the idea of viewing segmentation as reachability between indices.
- Shows how memoisation or BFS prevents exponential rework on overlapping subproblems.
- Forms the backbone for follow-ups like counting segmentations or returning actual sentences.
Thought Process
Visualise the state graph
Every index represents a state; edges connect start → end when substring(start, end) is in the dictionary.
Choose BFS over brute recursion
BFS (or DP) lets you avoid recomputing overlapping segments and keeps time at O(n²).
Prevent repeated work
Mark starting positions you have already explored so you do not enqueue them again.
Step-by-Step Reasoning
- Place every dictionary word into a hash set for O(1) lookups.
- Initialise a queue with start index 0 and a visited boolean array sized to s.
- Pop a start index; try every end index past it and enqueue any end that matches a dictionary word.
- If you ever enqueue s.length(), you can segment the entire string; otherwise exhaust the queue.
Dry Run
s = "leetcode", queue = [0]
Substring "leet" hits the dictionary; enqueue 4 and mark 0 visited.
start = 4
Substring "code" matches; enqueue 8 which equals s.length(), so return true.
Complexity Analysis
Time
O(n^2)
Space
O(n)
Why
There are O(n) start positions, each exploring up to O(n) end positions; the dictionary and visited array cost linear additional space.
Annotated Solution
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class WordBreak {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
boolean[] visited = new boolean[s.length()];
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(0);
while (!queue.isEmpty()) {
int start = queue.poll();
if (start == s.length()) {
return true;
}
if (visited[start]) {
continue;
}
for (int end = start + 1; end <= s.length(); end += 1) {
if (dict.contains(s.substring(start, end))) {
queue.offer(end);
}
}
visited[start] = true;
}
return false;
}
}Indices become graph nodes. BFS with a visited array ensures each start index is expanded at most once, keeping the runtime quadratic.
Common Pitfalls
- Neglecting the visited array leads to exponential queues on inputs with many repeated prefixes.
- Building substrings with StringBuilder but not trimming can produce false positives.
- Forgetting to add dictionary words to a set keeps lookups at O(k) per check.
Follow-Up Questions
- How do you return all possible segmentations instead of a boolean?
- Can you solve it with a bottom-up DP that runs in the same complexity?