DSA-132 · FOCUSED PRACTICE
Word Break
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 8157 deterministic checks. Learner drafts are not executed.
Understand the problem
Return whether text can be written as a concatenation of dictionary words, allowing each word to be reused. All text characters must be covered in order. Return only a boolean, not all segmentations.
- text and words must be non-null, and every dictionary entry must be non-null. Null values throw NullPointerException. text length is at most 2000; words has at most 1000 entries; each entry has length 1..2000; raw dictionary lengths total at most 100000. Violating a size or empty-word rule throws IllegalArgumentException, even for empty text.
- Matching is exact and case-sensitive over Java UTF-16 code units, with no normalization. All char values are allowed. Duplicate dictionary strings are allowed and do not change the boolean answer. The array and string values are read-only; words may be reused arbitrarily.
- The empty text returns true with any valid dictionary, including empty: the empty word sequence is a valid segmentation. A nonempty text and empty dictionary return false. Empty dictionary entries are rejected so every word edge advances a boundary. The recursive baseline is practical only for short inputs.
Examples
Input:
text="leetcode", words=["leet","code"]
Output:trueBoundary 4 is reachable through leet, then boundary 8 through code.
Input:
text="cars", words=["car","ca","rs"]
Output:trueThe longer local match car fails, while ca followed by rs covers the complete text.
Input:
text="catsandog", words=["cats","dog","sand","and","cat"]
Output:falseSeveral prefixes are reachable, but none reaches the final boundary.
Input:
text="", words=[]
Output:trueThe empty sequence covers the empty text.
Before you start
- Prefix boundaries and boolean reachability
- Trie terminal markers versus matching prefixes
Recognize the structure
Different word choices can reach the same text boundary; from that boundary, future segmentation feasibility depends only on the remaining text. Treat boundaries 0..n as vertices, with an edge i→j when text[i..j) is a complete dictionary word. The question is reachability of n from 0. A trie discovers only matching word edges without constructing and hashing every possible substring.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 142/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Draw vertices for boundaries between code units, including 0 and n.
Hint 2
A complete matching word is an edge from one boundary to a later boundary. Which boundary is reachable before reading anything?
Hint 3
Expand trie paths only from true starts, mark terminals at end+1, and keep matching longer words.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Enumerate matching next words without caching
At a starting boundary, try every dictionary entry whose whole text matches there using startsWith. Recurse after that word and succeed when a branch reaches n. The first successful branch can return true, but a long near-match ending in an impossible suffix repeats many boundaries exponentially. Duplicate words repeat work but cannot change a boolean. Every word is nonempty, so calls strictly advance and terminate. Verification compares only short strings with this recursive method. An independent oracle enumerates possible cut sets and tests the resulting whole pieces against a word set.
Improve the baseline
Define boundaries rather than character positions
reachable[j] means text[0..j) has a valid complete segmentation. reachable[0]=true represents the empty prefix. There are n+1 boundaries for n code units. A matching character prefix in the trie is not sufficient: a word edge ends only at a terminal node.
Build a private matching trie
Insert all words into nodes keyed by char. Equal words share a terminal, and words that are prefixes of others retain their own terminal marker and children. Track the longest dictionary word L during full validation. Building after validation ensures an invalid late entry cannot be hidden by an empty text or an earlier matching word.
Expand only already reachable boundaries
Visit starts in increasing order. If reachable[start] is false, no matching word beginning there can extend a valid segmentation, so skip it. Otherwise follow trie characters from start for at most L code units. Stop when a child is absent. Every terminal reached marks reachable[end+1]=true; continue matching because a longer word can also be useful.
Merge histories without losing future options
For cars and [car,ca,rs], start 0 discovers boundaries 2 and 3. Boundary 2 discovers 4 through rs; boundary 3 need not succeed. A single boolean per boundary merges all histories that arrive there, because word reuse means the future dictionary availability is identical for all of them.
Keep implementation cost honest
Trie traversal reads charAt directly and does not allocate substrings for lookup. A HashSet solution written with substring has construction and hashing costs that must be counted. This implementation uses expected constant-time HashMap child lookup and bounds traversal by L; it does not claim worst-case constant-time arbitrary dictionary operations.
Why it is correct
Base and sound edge extension
The empty prefix is segmentable by using no words. A true start boundary followed by a trie terminal supplies one whole dictionary word, so marking its end produces a valid segmentation. Trie prefixes without terminals never mark a boundary.
Completeness in increasing boundary order
Suppose a valid segmentation reaches boundary j. Its final word starts at some earlier boundary i, which is reachable by induction. The scan from i follows every character of that word and reaches its terminal before exceeding L, so it marks j. All edges advance because words are nonempty, ensuring i is processed before j.
Termination and final answer
Each start is visited once, and each matching scan examines at most min(n−start,L) characters. When all starts are done, every feasible word sequence has its terminal boundary marked and no infeasible one has been introduced. reachable[n] therefore answers exactly whether the full text is segmentable. No caller-owned value is changed.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
public final class Solution {
private Solution() {}
private static final class Node {
final Map<Character, Node> children = new HashMap<>();
boolean terminal;
}
private static int validate(String text, String[] words) {
Objects.requireNonNull(text, "text"); Objects.requireNonNull(words, "words");
if (text.length() > 2_000 || words.length > 1_000) throw new IllegalArgumentException("bounds");
int total = 0, longest = 0;
for (String word : words) {
Objects.requireNonNull(word, "word");
if (word.isEmpty() || word.length() > 2_000) throw new IllegalArgumentException("word length");
total += word.length(); longest = Math.max(longest, word.length());
}
if (total > 100_000) throw new IllegalArgumentException("dictionary too large");
return longest;
}
public static boolean wordBreak(String text, String[] words) {
int longest = validate(text, words);
Node root = new Node();
for (String word : words) {
Node node = root;
for (int i = 0; i < word.length(); i++) node = node.children.computeIfAbsent(word.charAt(i), key -> new Node());
node.terminal = true;
}
boolean[] reachable = new boolean[text.length() + 1];
reachable[0] = true;
for (int start = 0; start < text.length(); start++) {
if (!reachable[start]) continue;
Node node = root;
for (int end = start; end < text.length() && end - start < longest; end++) {
node = node.children.get(text.charAt(end));
if (node == null) break;
if (node.terminal) reachable[end + 1] = true;
}
}
return reachable[text.length()];
}
// Baseline: enumerate word choices without caching suffix answers.
public static boolean baseline(String text, String[] words) {
validate(text, words);
return segment(text, words, 0);
}
private static boolean segment(String text, String[] words, int start) {
if (start == text.length()) return true;
for (String word : words) if (text.startsWith(word, start) && segment(text, words, start + word.length())) return true;
return false;
}
}
Read the meaningful blocks
Validate the entire dictionary
The validation pass checks null entries, nonempty words, individual bounds, and total raw length, including duplicates. It returns the longest word length. This keeps contract checking separate from the early outcomes of matching.
Preserve terminal flags while building branches
computeIfAbsent creates private nodes and terminal=true records a complete word. A terminal does not stop insertion or later scanning, since another word may extend it. Duplicate insertions are idempotent for boolean recognition.
Expand with boundary indices
The outer index names the first code unit of a candidate word. On reading end, a terminal marks boundary end+1. continue skips unreachable starts; break ends only the current trie scan when a character path is absent. The return reads n, not the last character index.
Complexity
Let n be text length, S the raw total dictionary code units, and L the longest word (zero for an empty dictionary). Validation and trie construction cost expected O(S+1); matching costs expected O(n(min(n,L)+1)). Total expected time is O(S+n(min(n,L)+1)+1), and auxiliary space is O(S+n+1) for trie nodes/maps and the boundary array.
The recursive baseline has a conservative O((m+1)^(n+1)(L+1)) upper bound for m entries and O(n+1) live call-stack depth, besides validation. The bound is loose but exposes repeated suffix work. UTF-16 operations count code units, not Unicode characters or grapheme clusters; a different text model changes both preprocessing and state indices.
Exact-state walkthroughs
Reveal normal and boundary traces
A longer local word can fail
Input: {"text":"cars","words":["car","ca","rs"]} · Complete segmentation exists: true
Step 1 of 13: Build the private trie and mark the empty prefix reachable.
The figure shows matching prefix text instead of trie object identities. Only complete terminal words create edges between boundaries. All dictionary validation has already finished.
Phase: initial.
Text: "cars". The trie contains reusable complete dictionary words; L=3 bounds a matching walk.
Text code-unit positions — boundaries lie before and after them
- 0: "c"
- 1: "a"
- 2: "r"
- 3: "s"
Segmentable prefix boundaries 0..n
- 0: reachableempty prefix
- 1: not yet reachabletext[0..1)
- 2: not yet reachabletext[0..2)
- 3: not yet reachabletext[0..3)
- 4: not yet reachabletext[0..4)
Distinct terminal dictionary words
- "car"
- "ca"
- "rs"
A shorter terminal does not stop the trie walk. Boolean arrivals merge histories at the same boundary; words are not consumed. At completion, false means no segmentation, rather than merely an unvisited boundary.
| Variable | Value |
|---|---|
| input | {"text":"cars","words":["car","ca","rs"]} |
| phase | "initial" |
| dictionary | ["car","ca","rs"] |
| longest | 3 |
| reachable | [true,false,false,false,false] |
See the affected Java block
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.Objects; 4 5 public final class Solution { 6 private Solution() {} 7 private static final class Node { 8 final Map<Character, Node> children = new HashMap<>(); 9 boolean terminal; 10 } 11 private static int validate(String text, String[] words) { 12 Objects.requireNonNull(text, "text"); Objects.requireNonNull(words, "words"); 13 if (text.length() > 2_000 || words.length > 1_000) throw new IllegalArgumentException("bounds"); 14 int total = 0, longest = 0; 15 for (String word : words) { 16 Objects.requireNonNull(word, "word"); 17 if (word.isEmpty() || word.length() > 2_000) throw new IllegalArgumentException("word length"); 18 total += word.length(); longest = Math.max(longest, word.length()); 19 } 20 if (total > 100_000) throw new IllegalArgumentException("dictionary too large"); 21 return longest; 22 } 23 public static boolean wordBreak(String text, String[] words) { 24 int longest = validate(text, words); 25 Node root = new Node(); 26 for (String word : words) { 27 Node node = root; 28 for (int i = 0; i < word.length(); i++) node = node.children.computeIfAbsent(word.charAt(i), key -> new Node()); 29 node.terminal = true; 30 } 31 boolean[] reachable = new boolean[text.length() + 1]; 32 reachable[0] = true; 33 for (int start = 0; start < text.length(); start++) { 34 if (!reachable[start]) continue; 35 Node node = root; 36 for (int end = start; end < text.length() && end - start < longest; end++) { 37 node = node.children.get(text.charAt(end)); 38 if (node == null) break; 39 if (node.terminal) reachable[end + 1] = true; 40 } 41 } 42 return reachable[text.length()]; 43 } 44 // Baseline: enumerate word choices without caching suffix answers. 45 public static boolean baseline(String text, String[] words) { 46 validate(text, words); 47 return segment(text, words, 0); 48 } 49 private static boolean segment(String text, String[] words, int start) { 50 if (start == text.length()) return true; 51 for (String word : words) if (text.startsWith(word, start) && segment(text, words, start + word.length())) return true; 52 return false; 53 } 54 } 55
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Build the private trie and mark the empty prefix reachable.
The figure shows matching prefix text instead of trie object identities. Only complete terminal words create edges between boundaries. All dictionary validation has already finished.
- input
{"text":"cars","words":["car","ca","rs"]}- phase
"initial"- dictionary
["car","ca","rs"]- longest
3- reachable
[true,false,false,false,false]
- Expand a trie walk from one reachable boundary.
Every explored word edge begins after a valid segmented prefix. Finding a shorter terminal does not stop exploration of longer words.
- input
{"text":"cars","words":["car","ca","rs"]}- phase
"start"- dictionary
["car","ca","rs"]- longest
3- reachable
[true,false,false,false,false]- start
0
- The trie prefix exists but is not a whole word.
A terminal marks boundary end+1, not the last character index. Repeated arrivals merge into a boolean; words remain reusable.
- input
{"text":"cars","words":["car","ca","rs"]}- phase
"match"- dictionary
["car","ca","rs"]- longest
3- reachable
[true,false,false,false,false]- start
0- end
0- prefix
"c"- terminal
false- before
false
- A terminal word makes its end boundary reachable.
A terminal marks boundary end+1, not the last character index. Repeated arrivals merge into a boolean; words remain reusable.
- input
{"text":"cars","words":["car","ca","rs"]}- phase
"match"- dictionary
["car","ca","rs"]- longest
3- reachable
[true,false,true,false,false]- start
0- end
1- prefix
"ca"- terminal
true- before
false
- A terminal word makes its end boundary reachable.
A terminal marks boundary end+1, not the last character index. Repeated arrivals merge into a boolean; words remain reusable.
- input
{"text":"cars","words":["car","ca","rs"]}- phase
"match"- dictionary
["car","ca","rs"]- longest
3- reachable
[true,false,true,true,false]- start
0- end
2- prefix
"car"- terminal
true- before
false
- An unreachable boundary cannot start a complete segmentation.
Matching letters alone cannot repair the missing complete segmentation before this boundary.
- input
{"text":"cars","words":["car","ca","rs"]}- phase
"skip"- dictionary
["car","ca","rs"]- longest
3- reachable
[true,false,true,true,false]- start
1
- Expand a trie walk from one reachable boundary.
Every explored word edge begins after a valid segmented prefix. Finding a shorter terminal does not stop exploration of longer words.
- input
{"text":"cars","words":["car","ca","rs"]}- phase
"start"- dictionary
["car","ca","rs"]- longest
3- reachable
[true,false,true,true,false]- start
2
- The trie prefix exists but is not a whole word.
A terminal marks boundary end+1, not the last character index. Repeated arrivals merge into a boolean; words remain reusable.
- input
{"text":"cars","words":["car","ca","rs"]}- phase
"match"- dictionary
["car","ca","rs"]- longest
3- reachable
[true,false,true,true,false]- start
2- end
2- prefix
"r"- terminal
false- before
true
- A terminal word makes its end boundary reachable.
A terminal marks boundary end+1, not the last character index. Repeated arrivals merge into a boolean; words remain reusable.
- input
{"text":"cars","words":["car","ca","rs"]}- phase
"match"- dictionary
["car","ca","rs"]- longest
3- reachable
[true,false,true,true,true]- start
2- end
3- prefix
"rs"- terminal
true- before
false
- Expand a trie walk from one reachable boundary.
Every explored word edge begins after a valid segmented prefix. Finding a shorter terminal does not stop exploration of longer words.
- input
{"text":"cars","words":["car","ca","rs"]}- phase
"start"- dictionary
["car","ca","rs"]- longest
3- reachable
[true,false,true,true,true]- start
3
- The next character has no trie child; end this walk.
A longer word with this prefix cannot exist. Other reachable start boundaries remain eligible.
- input
{"text":"cars","words":["car","ca","rs"]}- phase
"missing"- dictionary
["car","ca","rs"]- longest
3- reachable
[true,false,true,true,true]- start
3- end
3- prefix
"s"
- Read the complete-text boundary.
All possible increasing word edges from reachable starts have been considered. Empty text needs no edge and returns true.
- input
{"text":"cars","words":["car","ca","rs"]}- phase
"complete"- dictionary
["car","ca","rs"]- longest
3- reachable
[true,false,true,true,true]
- Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
- result
true
A matching prefix is not a terminal
Input: {"text":"ab","words":["abc"]} · Complete segmentation exists: false
Step 1 of 7: Build the private trie and mark the empty prefix reachable.
The figure shows matching prefix text instead of trie object identities. Only complete terminal words create edges between boundaries. All dictionary validation has already finished.
Phase: initial.
Text: "ab". The trie contains reusable complete dictionary words; L=3 bounds a matching walk.
Text code-unit positions — boundaries lie before and after them
- 0: "a"
- 1: "b"
Segmentable prefix boundaries 0..n
- 0: reachableempty prefix
- 1: not yet reachabletext[0..1)
- 2: not yet reachabletext[0..2)
Distinct terminal dictionary words
- "abc"
A shorter terminal does not stop the trie walk. Boolean arrivals merge histories at the same boundary; words are not consumed. At completion, false means no segmentation, rather than merely an unvisited boundary.
| Variable | Value |
|---|---|
| input | {"text":"ab","words":["abc"]} |
| phase | "initial" |
| dictionary | ["abc"] |
| longest | 3 |
| reachable | [true,false,false] |
See the affected Java block
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.Objects; 4 5 public final class Solution { 6 private Solution() {} 7 private static final class Node { 8 final Map<Character, Node> children = new HashMap<>(); 9 boolean terminal; 10 } 11 private static int validate(String text, String[] words) { 12 Objects.requireNonNull(text, "text"); Objects.requireNonNull(words, "words"); 13 if (text.length() > 2_000 || words.length > 1_000) throw new IllegalArgumentException("bounds"); 14 int total = 0, longest = 0; 15 for (String word : words) { 16 Objects.requireNonNull(word, "word"); 17 if (word.isEmpty() || word.length() > 2_000) throw new IllegalArgumentException("word length"); 18 total += word.length(); longest = Math.max(longest, word.length()); 19 } 20 if (total > 100_000) throw new IllegalArgumentException("dictionary too large"); 21 return longest; 22 } 23 public static boolean wordBreak(String text, String[] words) { 24 int longest = validate(text, words); 25 Node root = new Node(); 26 for (String word : words) { 27 Node node = root; 28 for (int i = 0; i < word.length(); i++) node = node.children.computeIfAbsent(word.charAt(i), key -> new Node()); 29 node.terminal = true; 30 } 31 boolean[] reachable = new boolean[text.length() + 1]; 32 reachable[0] = true; 33 for (int start = 0; start < text.length(); start++) { 34 if (!reachable[start]) continue; 35 Node node = root; 36 for (int end = start; end < text.length() && end - start < longest; end++) { 37 node = node.children.get(text.charAt(end)); 38 if (node == null) break; 39 if (node.terminal) reachable[end + 1] = true; 40 } 41 } 42 return reachable[text.length()]; 43 } 44 // Baseline: enumerate word choices without caching suffix answers. 45 public static boolean baseline(String text, String[] words) { 46 validate(text, words); 47 return segment(text, words, 0); 48 } 49 private static boolean segment(String text, String[] words, int start) { 50 if (start == text.length()) return true; 51 for (String word : words) if (text.startsWith(word, start) && segment(text, words, start + word.length())) return true; 52 return false; 53 } 54 } 55
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Build the private trie and mark the empty prefix reachable.
The figure shows matching prefix text instead of trie object identities. Only complete terminal words create edges between boundaries. All dictionary validation has already finished.
- input
{"text":"ab","words":["abc"]}- phase
"initial"- dictionary
["abc"]- longest
3- reachable
[true,false,false]
- Expand a trie walk from one reachable boundary.
Every explored word edge begins after a valid segmented prefix. Finding a shorter terminal does not stop exploration of longer words.
- input
{"text":"ab","words":["abc"]}- phase
"start"- dictionary
["abc"]- longest
3- reachable
[true,false,false]- start
0
- The trie prefix exists but is not a whole word.
A terminal marks boundary end+1, not the last character index. Repeated arrivals merge into a boolean; words remain reusable.
- input
{"text":"ab","words":["abc"]}- phase
"match"- dictionary
["abc"]- longest
3- reachable
[true,false,false]- start
0- end
0- prefix
"a"- terminal
false- before
false
- The trie prefix exists but is not a whole word.
A terminal marks boundary end+1, not the last character index. Repeated arrivals merge into a boolean; words remain reusable.
- input
{"text":"ab","words":["abc"]}- phase
"match"- dictionary
["abc"]- longest
3- reachable
[true,false,false]- start
0- end
1- prefix
"ab"- terminal
false- before
false
- An unreachable boundary cannot start a complete segmentation.
Matching letters alone cannot repair the missing complete segmentation before this boundary.
- input
{"text":"ab","words":["abc"]}- phase
"skip"- dictionary
["abc"]- longest
3- reachable
[true,false,false]- start
1
- Read the complete-text boundary.
All possible increasing word edges from reachable starts have been considered. Empty text needs no edge and returns true.
- input
{"text":"ab","words":["abc"]}- phase
"complete"- dictionary
["abc"]- longest
3- reachable
[true,false,false]
- Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
- result
false
Empty text and dictionary
Input: {"text":"","words":[]} · Complete segmentation exists: true
Step 1 of 3: Build the private trie and mark the empty prefix reachable.
The figure shows matching prefix text instead of trie object identities. Only complete terminal words create edges between boundaries. All dictionary validation has already finished.
Phase: initial.
Text: "". The trie contains reusable complete dictionary words; L=0 bounds a matching walk.
Text code-unit positions — boundaries lie before and after them
Empty.
Segmentable prefix boundaries 0..n
- 0: reachableempty prefix
Distinct terminal dictionary words
Empty.
A shorter terminal does not stop the trie walk. Boolean arrivals merge histories at the same boundary; words are not consumed. At completion, false means no segmentation, rather than merely an unvisited boundary.
| Variable | Value |
|---|---|
| input | {"text":"","words":[]} |
| phase | "initial" |
| dictionary | [] |
| longest | 0 |
| reachable | [true] |
See the affected Java block
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.Objects; 4 5 public final class Solution { 6 private Solution() {} 7 private static final class Node { 8 final Map<Character, Node> children = new HashMap<>(); 9 boolean terminal; 10 } 11 private static int validate(String text, String[] words) { 12 Objects.requireNonNull(text, "text"); Objects.requireNonNull(words, "words"); 13 if (text.length() > 2_000 || words.length > 1_000) throw new IllegalArgumentException("bounds"); 14 int total = 0, longest = 0; 15 for (String word : words) { 16 Objects.requireNonNull(word, "word"); 17 if (word.isEmpty() || word.length() > 2_000) throw new IllegalArgumentException("word length"); 18 total += word.length(); longest = Math.max(longest, word.length()); 19 } 20 if (total > 100_000) throw new IllegalArgumentException("dictionary too large"); 21 return longest; 22 } 23 public static boolean wordBreak(String text, String[] words) { 24 int longest = validate(text, words); 25 Node root = new Node(); 26 for (String word : words) { 27 Node node = root; 28 for (int i = 0; i < word.length(); i++) node = node.children.computeIfAbsent(word.charAt(i), key -> new Node()); 29 node.terminal = true; 30 } 31 boolean[] reachable = new boolean[text.length() + 1]; 32 reachable[0] = true; 33 for (int start = 0; start < text.length(); start++) { 34 if (!reachable[start]) continue; 35 Node node = root; 36 for (int end = start; end < text.length() && end - start < longest; end++) { 37 node = node.children.get(text.charAt(end)); 38 if (node == null) break; 39 if (node.terminal) reachable[end + 1] = true; 40 } 41 } 42 return reachable[text.length()]; 43 } 44 // Baseline: enumerate word choices without caching suffix answers. 45 public static boolean baseline(String text, String[] words) { 46 validate(text, words); 47 return segment(text, words, 0); 48 } 49 private static boolean segment(String text, String[] words, int start) { 50 if (start == text.length()) return true; 51 for (String word : words) if (text.startsWith(word, start) && segment(text, words, start + word.length())) return true; 52 return false; 53 } 54 } 55
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Build the private trie and mark the empty prefix reachable.
The figure shows matching prefix text instead of trie object identities. Only complete terminal words create edges between boundaries. All dictionary validation has already finished.
- input
{"text":"","words":[]}- phase
"initial"- dictionary
[]- longest
0- reachable
[true]
- Read the complete-text boundary.
All possible increasing word edges from reachable starts have been considered. Empty text needs no edge and returns true.
- input
{"text":"","words":[]}- phase
"complete"- dictionary
[]- longest
0- reachable
[true]
- Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
- result
true
Reusable duplicate dictionary words
Input: {"text":"aaaa","words":["aa","aa"]} · Complete segmentation exists: true
Step 1 of 11: Build the private trie and mark the empty prefix reachable.
The figure shows matching prefix text instead of trie object identities. Only complete terminal words create edges between boundaries. All dictionary validation has already finished.
Phase: initial.
Text: "aaaa". The trie contains reusable complete dictionary words; L=2 bounds a matching walk.
Text code-unit positions — boundaries lie before and after them
- 0: "a"
- 1: "a"
- 2: "a"
- 3: "a"
Segmentable prefix boundaries 0..n
- 0: reachableempty prefix
- 1: not yet reachabletext[0..1)
- 2: not yet reachabletext[0..2)
- 3: not yet reachabletext[0..3)
- 4: not yet reachabletext[0..4)
Distinct terminal dictionary words
- "aa"
A shorter terminal does not stop the trie walk. Boolean arrivals merge histories at the same boundary; words are not consumed. At completion, false means no segmentation, rather than merely an unvisited boundary.
| Variable | Value |
|---|---|
| input | {"text":"aaaa","words":["aa","aa"]} |
| phase | "initial" |
| dictionary | ["aa"] |
| longest | 2 |
| reachable | [true,false,false,false,false] |
See the affected Java block
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.Objects; 4 5 public final class Solution { 6 private Solution() {} 7 private static final class Node { 8 final Map<Character, Node> children = new HashMap<>(); 9 boolean terminal; 10 } 11 private static int validate(String text, String[] words) { 12 Objects.requireNonNull(text, "text"); Objects.requireNonNull(words, "words"); 13 if (text.length() > 2_000 || words.length > 1_000) throw new IllegalArgumentException("bounds"); 14 int total = 0, longest = 0; 15 for (String word : words) { 16 Objects.requireNonNull(word, "word"); 17 if (word.isEmpty() || word.length() > 2_000) throw new IllegalArgumentException("word length"); 18 total += word.length(); longest = Math.max(longest, word.length()); 19 } 20 if (total > 100_000) throw new IllegalArgumentException("dictionary too large"); 21 return longest; 22 } 23 public static boolean wordBreak(String text, String[] words) { 24 int longest = validate(text, words); 25 Node root = new Node(); 26 for (String word : words) { 27 Node node = root; 28 for (int i = 0; i < word.length(); i++) node = node.children.computeIfAbsent(word.charAt(i), key -> new Node()); 29 node.terminal = true; 30 } 31 boolean[] reachable = new boolean[text.length() + 1]; 32 reachable[0] = true; 33 for (int start = 0; start < text.length(); start++) { 34 if (!reachable[start]) continue; 35 Node node = root; 36 for (int end = start; end < text.length() && end - start < longest; end++) { 37 node = node.children.get(text.charAt(end)); 38 if (node == null) break; 39 if (node.terminal) reachable[end + 1] = true; 40 } 41 } 42 return reachable[text.length()]; 43 } 44 // Baseline: enumerate word choices without caching suffix answers. 45 public static boolean baseline(String text, String[] words) { 46 validate(text, words); 47 return segment(text, words, 0); 48 } 49 private static boolean segment(String text, String[] words, int start) { 50 if (start == text.length()) return true; 51 for (String word : words) if (text.startsWith(word, start) && segment(text, words, start + word.length())) return true; 52 return false; 53 } 54 } 55
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Build the private trie and mark the empty prefix reachable.
The figure shows matching prefix text instead of trie object identities. Only complete terminal words create edges between boundaries. All dictionary validation has already finished.
- input
{"text":"aaaa","words":["aa","aa"]}- phase
"initial"- dictionary
["aa"]- longest
2- reachable
[true,false,false,false,false]
- Expand a trie walk from one reachable boundary.
Every explored word edge begins after a valid segmented prefix. Finding a shorter terminal does not stop exploration of longer words.
- input
{"text":"aaaa","words":["aa","aa"]}- phase
"start"- dictionary
["aa"]- longest
2- reachable
[true,false,false,false,false]- start
0
- The trie prefix exists but is not a whole word.
A terminal marks boundary end+1, not the last character index. Repeated arrivals merge into a boolean; words remain reusable.
- input
{"text":"aaaa","words":["aa","aa"]}- phase
"match"- dictionary
["aa"]- longest
2- reachable
[true,false,false,false,false]- start
0- end
0- prefix
"a"- terminal
false- before
false
- A terminal word makes its end boundary reachable.
A terminal marks boundary end+1, not the last character index. Repeated arrivals merge into a boolean; words remain reusable.
- input
{"text":"aaaa","words":["aa","aa"]}- phase
"match"- dictionary
["aa"]- longest
2- reachable
[true,false,true,false,false]- start
0- end
1- prefix
"aa"- terminal
true- before
false
- An unreachable boundary cannot start a complete segmentation.
Matching letters alone cannot repair the missing complete segmentation before this boundary.
- input
{"text":"aaaa","words":["aa","aa"]}- phase
"skip"- dictionary
["aa"]- longest
2- reachable
[true,false,true,false,false]- start
1
- Expand a trie walk from one reachable boundary.
Every explored word edge begins after a valid segmented prefix. Finding a shorter terminal does not stop exploration of longer words.
- input
{"text":"aaaa","words":["aa","aa"]}- phase
"start"- dictionary
["aa"]- longest
2- reachable
[true,false,true,false,false]- start
2
- The trie prefix exists but is not a whole word.
A terminal marks boundary end+1, not the last character index. Repeated arrivals merge into a boolean; words remain reusable.
- input
{"text":"aaaa","words":["aa","aa"]}- phase
"match"- dictionary
["aa"]- longest
2- reachable
[true,false,true,false,false]- start
2- end
2- prefix
"a"- terminal
false- before
false
- A terminal word makes its end boundary reachable.
A terminal marks boundary end+1, not the last character index. Repeated arrivals merge into a boolean; words remain reusable.
- input
{"text":"aaaa","words":["aa","aa"]}- phase
"match"- dictionary
["aa"]- longest
2- reachable
[true,false,true,false,true]- start
2- end
3- prefix
"aa"- terminal
true- before
false
- An unreachable boundary cannot start a complete segmentation.
Matching letters alone cannot repair the missing complete segmentation before this boundary.
- input
{"text":"aaaa","words":["aa","aa"]}- phase
"skip"- dictionary
["aa"]- longest
2- reachable
[true,false,true,false,true]- start
3
- Read the complete-text boundary.
All possible increasing word edges from reachable starts have been considered. Empty text needs no edge and returns true.
- input
{"text":"aaaa","words":["aa","aa"]}- phase
"complete"- dictionary
["aa"]- longest
2- reachable
[true,false,true,false,true]
- Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
- result
true
Case-sensitive Unicode units
Input: {"text":"αβ","words":["α","β"]} · Complete segmentation exists: true
Step 1 of 7: Build the private trie and mark the empty prefix reachable.
The figure shows matching prefix text instead of trie object identities. Only complete terminal words create edges between boundaries. All dictionary validation has already finished.
Phase: initial.
Text: "αβ". The trie contains reusable complete dictionary words; L=1 bounds a matching walk.
Text code-unit positions — boundaries lie before and after them
- 0: "α"
- 1: "β"
Segmentable prefix boundaries 0..n
- 0: reachableempty prefix
- 1: not yet reachabletext[0..1)
- 2: not yet reachabletext[0..2)
Distinct terminal dictionary words
- "α"
- "β"
A shorter terminal does not stop the trie walk. Boolean arrivals merge histories at the same boundary; words are not consumed. At completion, false means no segmentation, rather than merely an unvisited boundary.
| Variable | Value |
|---|---|
| input | {"text":"αβ","words":["α","β"]} |
| phase | "initial" |
| dictionary | ["α","β"] |
| longest | 1 |
| reachable | [true,false,false] |
See the affected Java block
1 import java.util.HashMap; 2 import java.util.Map; 3 import java.util.Objects; 4 5 public final class Solution { 6 private Solution() {} 7 private static final class Node { 8 final Map<Character, Node> children = new HashMap<>(); 9 boolean terminal; 10 } 11 private static int validate(String text, String[] words) { 12 Objects.requireNonNull(text, "text"); Objects.requireNonNull(words, "words"); 13 if (text.length() > 2_000 || words.length > 1_000) throw new IllegalArgumentException("bounds"); 14 int total = 0, longest = 0; 15 for (String word : words) { 16 Objects.requireNonNull(word, "word"); 17 if (word.isEmpty() || word.length() > 2_000) throw new IllegalArgumentException("word length"); 18 total += word.length(); longest = Math.max(longest, word.length()); 19 } 20 if (total > 100_000) throw new IllegalArgumentException("dictionary too large"); 21 return longest; 22 } 23 public static boolean wordBreak(String text, String[] words) { 24 int longest = validate(text, words); 25 Node root = new Node(); 26 for (String word : words) { 27 Node node = root; 28 for (int i = 0; i < word.length(); i++) node = node.children.computeIfAbsent(word.charAt(i), key -> new Node()); 29 node.terminal = true; 30 } 31 boolean[] reachable = new boolean[text.length() + 1]; 32 reachable[0] = true; 33 for (int start = 0; start < text.length(); start++) { 34 if (!reachable[start]) continue; 35 Node node = root; 36 for (int end = start; end < text.length() && end - start < longest; end++) { 37 node = node.children.get(text.charAt(end)); 38 if (node == null) break; 39 if (node.terminal) reachable[end + 1] = true; 40 } 41 } 42 return reachable[text.length()]; 43 } 44 // Baseline: enumerate word choices without caching suffix answers. 45 public static boolean baseline(String text, String[] words) { 46 validate(text, words); 47 return segment(text, words, 0); 48 } 49 private static boolean segment(String text, String[] words, int start) { 50 if (start == text.length()) return true; 51 for (String word : words) if (text.startsWith(word, start) && segment(text, words, start + word.length())) return true; 52 return false; 53 } 54 } 55
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Build the private trie and mark the empty prefix reachable.
The figure shows matching prefix text instead of trie object identities. Only complete terminal words create edges between boundaries. All dictionary validation has already finished.
- input
{"text":"αβ","words":["α","β"]}- phase
"initial"- dictionary
["α","β"]- longest
1- reachable
[true,false,false]
- Expand a trie walk from one reachable boundary.
Every explored word edge begins after a valid segmented prefix. Finding a shorter terminal does not stop exploration of longer words.
- input
{"text":"αβ","words":["α","β"]}- phase
"start"- dictionary
["α","β"]- longest
1- reachable
[true,false,false]- start
0
- A terminal word makes its end boundary reachable.
A terminal marks boundary end+1, not the last character index. Repeated arrivals merge into a boolean; words remain reusable.
- input
{"text":"αβ","words":["α","β"]}- phase
"match"- dictionary
["α","β"]- longest
1- reachable
[true,true,false]- start
0- end
0- prefix
"α"- terminal
true- before
false
- Expand a trie walk from one reachable boundary.
Every explored word edge begins after a valid segmented prefix. Finding a shorter terminal does not stop exploration of longer words.
- input
{"text":"αβ","words":["α","β"]}- phase
"start"- dictionary
["α","β"]- longest
1- reachable
[true,true,false]- start
1
- A terminal word makes its end boundary reachable.
A terminal marks boundary end+1, not the last character index. Repeated arrivals merge into a boolean; words remain reusable.
- input
{"text":"αβ","words":["α","β"]}- phase
"match"- dictionary
["α","β"]- longest
1- reachable
[true,true,true]- start
1- end
1- prefix
"β"- terminal
true- before
false
- Read the complete-text boundary.
All possible increasing word edges from reachable starts have been considered. Empty text needs no edge and returns true.
- input
{"text":"αβ","words":["α","β"]}- phase
"complete"- dictionary
["α","β"]- longest
1- reachable
[true,true,true]
- Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
- result
true
Test the contract
Input:
text="a", words=[]
Output:falseNo word edge leaves zero.
Input:
text="aaaa", words=["aa","aa"]
Output:trueReuse is allowed and duplicate values are harmless.
Input:
text="ab", words=["abc"]
Output:falseA nonterminal matching prefix is insufficient.
Input:
text="A", words=["a"]
Output:falseCase-sensitive matching.
Input:
text="αβ", words=["α","β"]
Output:trueBMP code units work without alphabet restrictions.
Input:
text="", words=[""]
Output:IllegalArgumentExceptionValidation precedes empty-text success.
Common mistakes and counterexamples
Choose the longest matching word greedily
Counterexample: cars with car, ca, rs fails after car but succeeds as ca|rs.
Keep every reachable boundary; a longer local word need not lead to a full segmentation.
Treat any trie prefix as a complete word
Counterexample: text="ab", words=["abc"] must be false.
Only terminal trie nodes create word edges.
Use each dictionary entry once
Counterexample: aaaa with [aa] is true through aa|aa.
The dictionary describes reusable word values, not consumable tokens.
Accept empty dictionary words or check only some entries
Counterexample: An empty word creates a zero-length recursive edge; invalid entries must be rejected even for empty text.
Validate all entries before constructing or traversing the trie.
Follow-ups
Return one segmentation.
When a boundary becomes reachable for the first time, store its predecessor start. Backtrack from n and reverse the pieces. Define a deterministic word/edge order for ties; the current trie scan supplies increasing endpoints from increasing starts, but the value-only API does not promise a particular witness.
Enumerate all segmentations.
Store the reachable word-edge DAG or use memoized suffix enumeration. Shared suffix feasibility can be cached, but all output strings or word lists still need output-sensitive time and space. Do not describe exponential output as eliminated by a boolean DP.
Dictionary is fixed across many queries or matching uses Unicode code points.
Reuse an immutable trie while allocating a fresh reachable array for each text. Account for build amortization separately. For code-point semantics, convert words and text to code-point arrays and map reconstructed offsets back to original strings; Java charAt and substring offsets alone do not implement that contract.