DSA-092 · Stop token lookup at the first terminal prefix while preserving original separators
Replace Words with Shortest Root
Core · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 20173 deterministic checks. Learner drafts are not executed.
Understand the problem
Replace every lowercase sentence token with its shortest dictionary root prefix, if one exists. Copy every original ASCII space exactly, including leading, repeated and trailing spaces.
- dictionary and sentence are nonnull. Dictionary roots are nonnull, nonempty lowercase-ASCII strings; duplicates are allowed. At most 10,000 roots, 100,000 total root characters, and root length at most 10,000 are size preconditions. Null roots throw NullPointerException; empty or unsupported roots throw IllegalArgumentException.
- The sentence has at most 100,000 characters and contains only lowercase ASCII letters and literal U+0020 spaces. A token is a maximal nonempty letter run; tabs, punctuation, uppercase and non-ASCII characters throw IllegalArgumentException. Empty and all-space sentences are valid.
- Preserve the dictionary array and its elements; do not sort caller input. Return exact replacement content with unchanged separators. Strings are immutable, so no returned-String identity/freshness guarantee is needed. Empty roots are rejected rather than silently replacing every token with empty text.
Examples
Input:
roots=[cat,bat,rat]; sentence=the cattle was rattled by the battery
Output:the cat was rat by the batEach token uses the shortest complete dictionary prefix, not merely an existing trie path.
Input:
roots=[cattle,cat,c,cat]; sentence=" cattle cat dog "
Output:" c c dog "Root c wins independent of insertion order, while all original spaces remain.
Input:
roots=[]; sentence=" a b "
Output:" a b "No roots exist; spacing and unmatched words remain exact.
Before you start
- Trie prefixes and terminal markers
- Half-open text spans and exact output formatting
Recognize the structure
Walking a token from left to right visits candidate roots in increasing length. Therefore the first terminal is the shortest match. Tokenization and replacement span selection must remain separate so skipped suffix letters cannot become new tokens or lose separators.
Try before revealing
Hint 1
Root lengths are encountered in increasing order while walking a token.
Hint 2
A trie path is valid only when a terminal is reached.
Hint 3
Scan the full token boundary, stop lookup at its first terminal, and copy separators directly.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Compare each token against all roots
Scan maximal letter runs while copying each space. For a token, test every dictionary root that is no longer than the best current candidate and retain the minimum matching prefix length. For cattle with roots cattle,cat,c, each shorter matching candidate improves the span until c remains. This repeats root comparisons across tokens; the trie shares their prefixes.
Improve the baseline
Build complete-root terminals
Insert every validated root and mark only its final node. Duplicate roots are idempotent, and a longer insertion does not make its intermediate paths valid roots.
Capture original token boundaries
Copy spaces individually. On a letter, find the maximal [start,end) token and keep the outer cursor at end while a separate index probes root prefixes.
Stop at the first terminal or missing edge
A terminal gives the shortest root span [start,j+1). A missing edge rules out all longer roots. Append that chosen span or the entire original token, then resume at its original end.
Why it is correct
Prefix invariant
After j−start+1 successful edge steps, the current node represents exactly that many leading characters of the current token. No other dictionary prefix can match a different leading sequence.
Shortest-match proof
Successful steps visit depths in increasing order. The first terminal is therefore the minimum positive matching root length; if an edge is absent, every longer matching root would need that edge and is impossible.
Exact separator preservation
The outer scan partitions the sentence into individual space characters and maximal letter runs. Each space is copied once in position order; each token contributes exactly its chosen prefix or itself. The original end cursor prevents its removed suffix from being rescanned.
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.*;
public final class Solution {
private static final class Node { final Node[] children = new Node[26]; boolean terminal; }
private static void validate(String[] dictionary, String sentence) {
Objects.requireNonNull(dictionary,"dictionary"); Objects.requireNonNull(sentence,"sentence");
for (String word : dictionary) {
Objects.requireNonNull(word,"root");
if (word.isEmpty()) throw new IllegalArgumentException("empty root");
for (int i=0;i<word.length();i++) if (word.charAt(i) < 'a' || word.charAt(i) > 'z') throw new IllegalArgumentException("invalid root letter");
}
for (int i=0;i<sentence.length();i++) { char c=sentence.charAt(i); if (c != ' ' && (c < 'a' || c > 'z')) throw new IllegalArgumentException("invalid sentence character"); }
}
public static String replace(String[] dictionary, String sentence) {
validate(dictionary,sentence);
Node root = new Node();
for (String word : dictionary) {
Node node = root;
for (int i=0;i<word.length();i++) {
int slot=word.charAt(i)-'a';
if (node.children[slot] == null) node.children[slot] = new Node();
node=node.children[slot];
}
node.terminal=true;
}
StringBuilder output = new StringBuilder();
for (int i=0;i<sentence.length();) {
if (sentence.charAt(i) == ' ') { output.append(' '); i++; continue; }
int start=i;
while (i<sentence.length() && sentence.charAt(i) != ' ') i++;
Node node=root; int replacementEnd=-1;
for (int j=start;j<i;j++) {
node=node.children[sentence.charAt(j)-'a'];
if (node == null) break;
if (node.terminal) { replacementEnd=j+1; break; }
}
output.append(sentence,start,replacementEnd < 0 ? i : replacementEnd);
}
return output.toString();
}
public static String baseline(String[] dictionary, String sentence) {
validate(dictionary,sentence);
StringBuilder output = new StringBuilder();
for (int i=0;i<sentence.length();) {
if (sentence.charAt(i) == ' ') { output.append(' '); i++; continue; }
int start=i; while(i<sentence.length() && sentence.charAt(i) != ' ') i++;
int length=i-start;
for (String root : dictionary) if (root.length() <= length && sentence.startsWith(root,start)) length=root.length();
output.append(sentence,start,start+length);
}
return output.toString();
}
}
Read the meaningful blocks
Root path is not a complete root
Empty roots are invalid; an internal path becomes a replacement only when terminal is true.
Keep scan cursor and probe index distinct
The scan reaches token end before the trie walk. Stopping prefix lookup early must not reset the outer cursor to the shorter replacement length.
Append spans rather than normalizing tokens
StringBuilder.append(sentence,start,end) avoids per-token substring arrays and preserves separator content without split/join assumptions.
Complexity
With S total dictionary characters and n sentence length, trie construction, full validation, token scanning, prefix lookup and output copying total O(S+n) time for fixed alphabet 26. Prefix lookup examines at most the original token length, and output length is at most n.
Trie state is O(S); StringBuilder construction space and returned text are O(n) worst case, so peak auxiliary storage including the builder is O(S+n), plus the final String output. Baseline worst-case time is O(S+n+W·S) for W tokens, accounting for character comparisons against roots; it uses O(n) builder space and no trie.
Exact-state walkthroughs
Reveal normal and boundary traces
First terminal replaces each complete original token
Input: {"dictionary":["cat","bat","rat"],"sentence":"the cattle was rattled by the battery"} · Exact replacement text: "the cat was rat by the bat"
Step 1 of 36: Build root terminals without changing dictionary order.
The root path is not terminal because empty roots are rejected. The first terminal encountered on a token path is the shortest matching root.
Phase: initial.
Trie paths — sorted logical display
- (root / empty path)prefix path only
- bprefix path only
- baprefix path only
- batterminal word
- cprefix path only
- caprefix path only
- catterminal word
- rprefix path only
- raprefix path only
- ratterminal word
Input with each space shown as ·: the·cattle·was·rattled·by·the·battery
Output so far with spaces shown as ·: (empty)
Original scan boundary: 0. Token span: none. Replacement end: no terminal selected.
Token bounds are half-open. The original scan already reaches the whole token end before the separate trie probe runs. The first terminal gives the shortest complete root; its discarded suffix is not rescanned. The · symbols are display markers only; Java returns actual unchanged space characters.
Path cards represent shared dictionary prefixes, not board cells or dictionary occurrence order. Complete exact state and equivalent static steps remain available below.
| Variable | Value |
|---|---|
| dictionary | ["cat","bat","rat"] |
| sentence | "the cattle was rattled by the battery" |
| paths | ["","b","ba","bat","c","ca","cat","r","ra","rat"] |
| terminals | ["bat","cat","rat"] |
| cursor | 0 |
| output | "" |
| prefix | null |
| tokenStart | null |
| tokenEnd | null |
| replacementEnd | -1 |
| phase | "initial" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Node { final Node[] children = new Node[26]; boolean terminal; } 4 private static void validate(String[] dictionary, String sentence) { 5 Objects.requireNonNull(dictionary,"dictionary"); Objects.requireNonNull(sentence,"sentence"); 6 for (String word : dictionary) { 7 Objects.requireNonNull(word,"root"); 8 if (word.isEmpty()) throw new IllegalArgumentException("empty root"); 9 for (int i=0;i<word.length();i++) if (word.charAt(i) < 'a' || word.charAt(i) > 'z') throw new IllegalArgumentException("invalid root letter"); 10 } 11 for (int i=0;i<sentence.length();i++) { char c=sentence.charAt(i); if (c != ' ' && (c < 'a' || c > 'z')) throw new IllegalArgumentException("invalid sentence character"); } 12 } 13 public static String replace(String[] dictionary, String sentence) { 14 validate(dictionary,sentence); 15 Node root = new Node(); 16 for (String word : dictionary) { 17 Node node = root; 18 for (int i=0;i<word.length();i++) { 19 int slot=word.charAt(i)-'a'; 20 if (node.children[slot] == null) node.children[slot] = new Node(); 21 node=node.children[slot]; 22 } 23 node.terminal=true; 24 } 25 StringBuilder output = new StringBuilder(); 26 for (int i=0;i<sentence.length();) { 27 if (sentence.charAt(i) == ' ') { output.append(' '); i++; continue; } 28 int start=i; 29 while (i<sentence.length() && sentence.charAt(i) != ' ') i++; 30 Node node=root; int replacementEnd=-1; 31 for (int j=start;j<i;j++) { 32 node=node.children[sentence.charAt(j)-'a']; 33 if (node == null) break; 34 if (node.terminal) { replacementEnd=j+1; break; } 35 } 36 output.append(sentence,start,replacementEnd < 0 ? i : replacementEnd); 37 } 38 return output.toString(); 39 } 40 public static String baseline(String[] dictionary, String sentence) { 41 validate(dictionary,sentence); 42 StringBuilder output = new StringBuilder(); 43 for (int i=0;i<sentence.length();) { 44 if (sentence.charAt(i) == ' ') { output.append(' '); i++; continue; } 45 int start=i; while(i<sentence.length() && sentence.charAt(i) != ' ') i++; 46 int length=i-start; 47 for (String root : dictionary) if (root.length() <= length && sentence.startsWith(root,start)) length=root.length(); 48 output.append(sentence,start,start+length); 49 } 50 return output.toString(); 51 } 52 } 53
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Build root terminals without changing dictionary order.
The root path is not terminal because empty roots are rejected. The first terminal encountered on a token path is the shortest matching root.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
0- output
""- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"initial"
- Find the whole original token boundary before probing roots.
cursor is already at the original token end; output does not include that token until emit. Token bounds are half-open.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
3- output
""- prefix
""- tokenStart
0- tokenEnd
3- replacementEnd
-1- phase
"token"
- Stop root lookup on a missing edge.
Without a trie edge, no longer dictionary root can match this token prefix. The entire original token will be copied.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
3- output
""- prefix
null- tokenStart
0- tokenEnd
3- replacementEnd
-1- phase
"missing"- probe
0
- Append the chosen root span or the complete untouched token.
The scan still resumes at the original token end, so discarded suffix letters never become separate tokens.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
3- output
"the"- prefix
null- tokenStart
0- tokenEnd
3- replacementEnd
-1- phase
"emit"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
4- output
"the "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Find the whole original token boundary before probing roots.
cursor is already at the original token end; output does not include that token until emit. Token bounds are half-open.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
10- output
"the "- prefix
""- tokenStart
4- tokenEnd
10- replacementEnd
-1- phase
"token"
- Continue through a nonterminal prefix path.
Path existence alone does not authorize a replacement.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
10- output
"the "- prefix
"c"- tokenStart
4- tokenEnd
10- replacementEnd
-1- phase
"prefix"- probe
4
- Continue through a nonterminal prefix path.
Path existence alone does not authorize a replacement.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
10- output
"the "- prefix
"ca"- tokenStart
4- tokenEnd
10- replacementEnd
-1- phase
"prefix"- probe
5
- Stop at the first terminal, before any longer matching root.
First-terminal depth is minimum root length; dictionary insertion order and duplicate roots cannot change the chosen prefix.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
10- output
"the "- prefix
"cat"- tokenStart
4- tokenEnd
10- replacementEnd
7- phase
"terminal"- probe
6
- Append the chosen root span or the complete untouched token.
The scan still resumes at the original token end, so discarded suffix letters never become separate tokens.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
10- output
"the cat"- prefix
"cat"- tokenStart
4- tokenEnd
10- replacementEnd
7- phase
"emit"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
11- output
"the cat "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Find the whole original token boundary before probing roots.
cursor is already at the original token end; output does not include that token until emit. Token bounds are half-open.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
14- output
"the cat "- prefix
""- tokenStart
11- tokenEnd
14- replacementEnd
-1- phase
"token"
- Stop root lookup on a missing edge.
Without a trie edge, no longer dictionary root can match this token prefix. The entire original token will be copied.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
14- output
"the cat "- prefix
null- tokenStart
11- tokenEnd
14- replacementEnd
-1- phase
"missing"- probe
11
- Append the chosen root span or the complete untouched token.
The scan still resumes at the original token end, so discarded suffix letters never become separate tokens.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
14- output
"the cat was"- prefix
null- tokenStart
11- tokenEnd
14- replacementEnd
-1- phase
"emit"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
15- output
"the cat was "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Find the whole original token boundary before probing roots.
cursor is already at the original token end; output does not include that token until emit. Token bounds are half-open.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
22- output
"the cat was "- prefix
""- tokenStart
15- tokenEnd
22- replacementEnd
-1- phase
"token"
- Continue through a nonterminal prefix path.
Path existence alone does not authorize a replacement.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
22- output
"the cat was "- prefix
"r"- tokenStart
15- tokenEnd
22- replacementEnd
-1- phase
"prefix"- probe
15
- Continue through a nonterminal prefix path.
Path existence alone does not authorize a replacement.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
22- output
"the cat was "- prefix
"ra"- tokenStart
15- tokenEnd
22- replacementEnd
-1- phase
"prefix"- probe
16
- Stop at the first terminal, before any longer matching root.
First-terminal depth is minimum root length; dictionary insertion order and duplicate roots cannot change the chosen prefix.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
22- output
"the cat was "- prefix
"rat"- tokenStart
15- tokenEnd
22- replacementEnd
18- phase
"terminal"- probe
17
- Append the chosen root span or the complete untouched token.
The scan still resumes at the original token end, so discarded suffix letters never become separate tokens.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
22- output
"the cat was rat"- prefix
"rat"- tokenStart
15- tokenEnd
22- replacementEnd
18- phase
"emit"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
23- output
"the cat was rat "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Find the whole original token boundary before probing roots.
cursor is already at the original token end; output does not include that token until emit. Token bounds are half-open.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
25- output
"the cat was rat "- prefix
""- tokenStart
23- tokenEnd
25- replacementEnd
-1- phase
"token"
- Continue through a nonterminal prefix path.
Path existence alone does not authorize a replacement.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
25- output
"the cat was rat "- prefix
"b"- tokenStart
23- tokenEnd
25- replacementEnd
-1- phase
"prefix"- probe
23
- Stop root lookup on a missing edge.
Without a trie edge, no longer dictionary root can match this token prefix. The entire original token will be copied.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
25- output
"the cat was rat "- prefix
null- tokenStart
23- tokenEnd
25- replacementEnd
-1- phase
"missing"- probe
24
- Append the chosen root span or the complete untouched token.
The scan still resumes at the original token end, so discarded suffix letters never become separate tokens.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
25- output
"the cat was rat by"- prefix
null- tokenStart
23- tokenEnd
25- replacementEnd
-1- phase
"emit"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
26- output
"the cat was rat by "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Find the whole original token boundary before probing roots.
cursor is already at the original token end; output does not include that token until emit. Token bounds are half-open.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
29- output
"the cat was rat by "- prefix
""- tokenStart
26- tokenEnd
29- replacementEnd
-1- phase
"token"
- Stop root lookup on a missing edge.
Without a trie edge, no longer dictionary root can match this token prefix. The entire original token will be copied.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
29- output
"the cat was rat by "- prefix
null- tokenStart
26- tokenEnd
29- replacementEnd
-1- phase
"missing"- probe
26
- Append the chosen root span or the complete untouched token.
The scan still resumes at the original token end, so discarded suffix letters never become separate tokens.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
29- output
"the cat was rat by the"- prefix
null- tokenStart
26- tokenEnd
29- replacementEnd
-1- phase
"emit"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
30- output
"the cat was rat by the "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Find the whole original token boundary before probing roots.
cursor is already at the original token end; output does not include that token until emit. Token bounds are half-open.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
37- output
"the cat was rat by the "- prefix
""- tokenStart
30- tokenEnd
37- replacementEnd
-1- phase
"token"
- Continue through a nonterminal prefix path.
Path existence alone does not authorize a replacement.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
37- output
"the cat was rat by the "- prefix
"b"- tokenStart
30- tokenEnd
37- replacementEnd
-1- phase
"prefix"- probe
30
- Continue through a nonterminal prefix path.
Path existence alone does not authorize a replacement.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
37- output
"the cat was rat by the "- prefix
"ba"- tokenStart
30- tokenEnd
37- replacementEnd
-1- phase
"prefix"- probe
31
- Stop at the first terminal, before any longer matching root.
First-terminal depth is minimum root length; dictionary insertion order and duplicate roots cannot change the chosen prefix.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
37- output
"the cat was rat by the "- prefix
"bat"- tokenStart
30- tokenEnd
37- replacementEnd
33- phase
"terminal"- probe
32
- Append the chosen root span or the complete untouched token.
The scan still resumes at the original token end, so discarded suffix letters never become separate tokens.
- dictionary
["cat","bat","rat"]- sentence
"the cattle was rattled by the battery"- paths
["","b","ba","bat","c","ca","cat","r","ra","rat"]- terminals
["bat","cat","rat"]- cursor
37- output
"the cat was rat by the bat"- prefix
"bat"- tokenStart
30- tokenEnd
37- replacementEnd
33- phase
"emit"
- Return the documented operation outcomes, unique found words, or exact replacement text.
Trie path displays are logical views. Board-path visited state and terminal flags have different lifetimes; no caller-owned input is mutated.
- result
"the cat was rat by the bat"
Shortest root and exact repeated spaces
Input: {"dictionary":["cattle","cat","c","cat"],"sentence":" cattle cat dog "} · Exact replacement text: " c c dog "
Step 1 of 17: Build root terminals without changing dictionary order.
The root path is not terminal because empty roots are rejected. The first terminal encountered on a token path is the shortest matching root.
Phase: initial.
Trie paths — sorted logical display
- (root / empty path)prefix path only
- cterminal word
- caprefix path only
- catterminal word
- cattprefix path only
- cattlprefix path only
- cattleterminal word
Input with each space shown as ·: ··cattle··cat·dog·
Output so far with spaces shown as ·: (empty)
Original scan boundary: 0. Token span: none. Replacement end: no terminal selected.
Token bounds are half-open. The original scan already reaches the whole token end before the separate trie probe runs. The first terminal gives the shortest complete root; its discarded suffix is not rescanned. The · symbols are display markers only; Java returns actual unchanged space characters.
Path cards represent shared dictionary prefixes, not board cells or dictionary occurrence order. Complete exact state and equivalent static steps remain available below.
| Variable | Value |
|---|---|
| dictionary | ["cattle","cat","c","cat"] |
| sentence | " cattle cat dog " |
| paths | ["","c","ca","cat","catt","cattl","cattle"] |
| terminals | ["c","cat","cattle"] |
| cursor | 0 |
| output | "" |
| prefix | null |
| tokenStart | null |
| tokenEnd | null |
| replacementEnd | -1 |
| phase | "initial" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Node { final Node[] children = new Node[26]; boolean terminal; } 4 private static void validate(String[] dictionary, String sentence) { 5 Objects.requireNonNull(dictionary,"dictionary"); Objects.requireNonNull(sentence,"sentence"); 6 for (String word : dictionary) { 7 Objects.requireNonNull(word,"root"); 8 if (word.isEmpty()) throw new IllegalArgumentException("empty root"); 9 for (int i=0;i<word.length();i++) if (word.charAt(i) < 'a' || word.charAt(i) > 'z') throw new IllegalArgumentException("invalid root letter"); 10 } 11 for (int i=0;i<sentence.length();i++) { char c=sentence.charAt(i); if (c != ' ' && (c < 'a' || c > 'z')) throw new IllegalArgumentException("invalid sentence character"); } 12 } 13 public static String replace(String[] dictionary, String sentence) { 14 validate(dictionary,sentence); 15 Node root = new Node(); 16 for (String word : dictionary) { 17 Node node = root; 18 for (int i=0;i<word.length();i++) { 19 int slot=word.charAt(i)-'a'; 20 if (node.children[slot] == null) node.children[slot] = new Node(); 21 node=node.children[slot]; 22 } 23 node.terminal=true; 24 } 25 StringBuilder output = new StringBuilder(); 26 for (int i=0;i<sentence.length();) { 27 if (sentence.charAt(i) == ' ') { output.append(' '); i++; continue; } 28 int start=i; 29 while (i<sentence.length() && sentence.charAt(i) != ' ') i++; 30 Node node=root; int replacementEnd=-1; 31 for (int j=start;j<i;j++) { 32 node=node.children[sentence.charAt(j)-'a']; 33 if (node == null) break; 34 if (node.terminal) { replacementEnd=j+1; break; } 35 } 36 output.append(sentence,start,replacementEnd < 0 ? i : replacementEnd); 37 } 38 return output.toString(); 39 } 40 public static String baseline(String[] dictionary, String sentence) { 41 validate(dictionary,sentence); 42 StringBuilder output = new StringBuilder(); 43 for (int i=0;i<sentence.length();) { 44 if (sentence.charAt(i) == ' ') { output.append(' '); i++; continue; } 45 int start=i; while(i<sentence.length() && sentence.charAt(i) != ' ') i++; 46 int length=i-start; 47 for (String root : dictionary) if (root.length() <= length && sentence.startsWith(root,start)) length=root.length(); 48 output.append(sentence,start,start+length); 49 } 50 return output.toString(); 51 } 52 } 53
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Build root terminals without changing dictionary order.
The root path is not terminal because empty roots are rejected. The first terminal encountered on a token path is the shortest matching root.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
0- output
""- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"initial"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
1- output
" "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
2- output
" "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Find the whole original token boundary before probing roots.
cursor is already at the original token end; output does not include that token until emit. Token bounds are half-open.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
8- output
" "- prefix
""- tokenStart
2- tokenEnd
8- replacementEnd
-1- phase
"token"
- Stop at the first terminal, before any longer matching root.
First-terminal depth is minimum root length; dictionary insertion order and duplicate roots cannot change the chosen prefix.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
8- output
" "- prefix
"c"- tokenStart
2- tokenEnd
8- replacementEnd
3- phase
"terminal"- probe
2
- Append the chosen root span or the complete untouched token.
The scan still resumes at the original token end, so discarded suffix letters never become separate tokens.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
8- output
" c"- prefix
"c"- tokenStart
2- tokenEnd
8- replacementEnd
3- phase
"emit"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
9- output
" c "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
10- output
" c "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Find the whole original token boundary before probing roots.
cursor is already at the original token end; output does not include that token until emit. Token bounds are half-open.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
13- output
" c "- prefix
""- tokenStart
10- tokenEnd
13- replacementEnd
-1- phase
"token"
- Stop at the first terminal, before any longer matching root.
First-terminal depth is minimum root length; dictionary insertion order and duplicate roots cannot change the chosen prefix.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
13- output
" c "- prefix
"c"- tokenStart
10- tokenEnd
13- replacementEnd
11- phase
"terminal"- probe
10
- Append the chosen root span or the complete untouched token.
The scan still resumes at the original token end, so discarded suffix letters never become separate tokens.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
13- output
" c c"- prefix
"c"- tokenStart
10- tokenEnd
13- replacementEnd
11- phase
"emit"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
14- output
" c c "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Find the whole original token boundary before probing roots.
cursor is already at the original token end; output does not include that token until emit. Token bounds are half-open.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
17- output
" c c "- prefix
""- tokenStart
14- tokenEnd
17- replacementEnd
-1- phase
"token"
- Stop root lookup on a missing edge.
Without a trie edge, no longer dictionary root can match this token prefix. The entire original token will be copied.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
17- output
" c c "- prefix
null- tokenStart
14- tokenEnd
17- replacementEnd
-1- phase
"missing"- probe
14
- Append the chosen root span or the complete untouched token.
The scan still resumes at the original token end, so discarded suffix letters never become separate tokens.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
17- output
" c c dog"- prefix
null- tokenStart
14- tokenEnd
17- replacementEnd
-1- phase
"emit"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["cattle","cat","c","cat"]- sentence
" cattle cat dog "- paths
["","c","ca","cat","catt","cattl","cattle"]- terminals
["c","cat","cattle"]- cursor
18- output
" c c dog "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Return the documented operation outcomes, unique found words, or exact replacement text.
Trie path displays are logical views. Board-path visited state and terminal flags have different lifetimes; no caller-owned input is mutated.
- result
" c c dog "
Empty roots collection leaves tokens unchanged
Input: {"dictionary":[],"sentence":" a b "} · Exact replacement text: " a b "
Step 1 of 12: Build root terminals without changing dictionary order.
The root path is not terminal because empty roots are rejected. The first terminal encountered on a token path is the shortest matching root.
Phase: initial.
Trie paths — sorted logical display
- (root / empty path)prefix path only
Input with each space shown as ·: ·a··b·
Output so far with spaces shown as ·: (empty)
Original scan boundary: 0. Token span: none. Replacement end: no terminal selected.
Token bounds are half-open. The original scan already reaches the whole token end before the separate trie probe runs. The first terminal gives the shortest complete root; its discarded suffix is not rescanned. The · symbols are display markers only; Java returns actual unchanged space characters.
Path cards represent shared dictionary prefixes, not board cells or dictionary occurrence order. Complete exact state and equivalent static steps remain available below.
| Variable | Value |
|---|---|
| dictionary | [] |
| sentence | " a b " |
| paths | [""] |
| terminals | [] |
| cursor | 0 |
| output | "" |
| prefix | null |
| tokenStart | null |
| tokenEnd | null |
| replacementEnd | -1 |
| phase | "initial" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Node { final Node[] children = new Node[26]; boolean terminal; } 4 private static void validate(String[] dictionary, String sentence) { 5 Objects.requireNonNull(dictionary,"dictionary"); Objects.requireNonNull(sentence,"sentence"); 6 for (String word : dictionary) { 7 Objects.requireNonNull(word,"root"); 8 if (word.isEmpty()) throw new IllegalArgumentException("empty root"); 9 for (int i=0;i<word.length();i++) if (word.charAt(i) < 'a' || word.charAt(i) > 'z') throw new IllegalArgumentException("invalid root letter"); 10 } 11 for (int i=0;i<sentence.length();i++) { char c=sentence.charAt(i); if (c != ' ' && (c < 'a' || c > 'z')) throw new IllegalArgumentException("invalid sentence character"); } 12 } 13 public static String replace(String[] dictionary, String sentence) { 14 validate(dictionary,sentence); 15 Node root = new Node(); 16 for (String word : dictionary) { 17 Node node = root; 18 for (int i=0;i<word.length();i++) { 19 int slot=word.charAt(i)-'a'; 20 if (node.children[slot] == null) node.children[slot] = new Node(); 21 node=node.children[slot]; 22 } 23 node.terminal=true; 24 } 25 StringBuilder output = new StringBuilder(); 26 for (int i=0;i<sentence.length();) { 27 if (sentence.charAt(i) == ' ') { output.append(' '); i++; continue; } 28 int start=i; 29 while (i<sentence.length() && sentence.charAt(i) != ' ') i++; 30 Node node=root; int replacementEnd=-1; 31 for (int j=start;j<i;j++) { 32 node=node.children[sentence.charAt(j)-'a']; 33 if (node == null) break; 34 if (node.terminal) { replacementEnd=j+1; break; } 35 } 36 output.append(sentence,start,replacementEnd < 0 ? i : replacementEnd); 37 } 38 return output.toString(); 39 } 40 public static String baseline(String[] dictionary, String sentence) { 41 validate(dictionary,sentence); 42 StringBuilder output = new StringBuilder(); 43 for (int i=0;i<sentence.length();) { 44 if (sentence.charAt(i) == ' ') { output.append(' '); i++; continue; } 45 int start=i; while(i<sentence.length() && sentence.charAt(i) != ' ') i++; 46 int length=i-start; 47 for (String root : dictionary) if (root.length() <= length && sentence.startsWith(root,start)) length=root.length(); 48 output.append(sentence,start,start+length); 49 } 50 return output.toString(); 51 } 52 } 53
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Build root terminals without changing dictionary order.
The root path is not terminal because empty roots are rejected. The first terminal encountered on a token path is the shortest matching root.
- dictionary
[]- sentence
" a b "- paths
[""]- terminals
[]- cursor
0- output
""- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"initial"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
[]- sentence
" a b "- paths
[""]- terminals
[]- cursor
1- output
" "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Find the whole original token boundary before probing roots.
cursor is already at the original token end; output does not include that token until emit. Token bounds are half-open.
- dictionary
[]- sentence
" a b "- paths
[""]- terminals
[]- cursor
2- output
" "- prefix
""- tokenStart
1- tokenEnd
2- replacementEnd
-1- phase
"token"
- Stop root lookup on a missing edge.
Without a trie edge, no longer dictionary root can match this token prefix. The entire original token will be copied.
- dictionary
[]- sentence
" a b "- paths
[""]- terminals
[]- cursor
2- output
" "- prefix
null- tokenStart
1- tokenEnd
2- replacementEnd
-1- phase
"missing"- probe
1
- Append the chosen root span or the complete untouched token.
The scan still resumes at the original token end, so discarded suffix letters never become separate tokens.
- dictionary
[]- sentence
" a b "- paths
[""]- terminals
[]- cursor
2- output
" a"- prefix
null- tokenStart
1- tokenEnd
2- replacementEnd
-1- phase
"emit"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
[]- sentence
" a b "- paths
[""]- terminals
[]- cursor
3- output
" a "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
[]- sentence
" a b "- paths
[""]- terminals
[]- cursor
4- output
" a "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Find the whole original token boundary before probing roots.
cursor is already at the original token end; output does not include that token until emit. Token bounds are half-open.
- dictionary
[]- sentence
" a b "- paths
[""]- terminals
[]- cursor
5- output
" a "- prefix
""- tokenStart
4- tokenEnd
5- replacementEnd
-1- phase
"token"
- Stop root lookup on a missing edge.
Without a trie edge, no longer dictionary root can match this token prefix. The entire original token will be copied.
- dictionary
[]- sentence
" a b "- paths
[""]- terminals
[]- cursor
5- output
" a "- prefix
null- tokenStart
4- tokenEnd
5- replacementEnd
-1- phase
"missing"- probe
4
- Append the chosen root span or the complete untouched token.
The scan still resumes at the original token end, so discarded suffix letters never become separate tokens.
- dictionary
[]- sentence
" a b "- paths
[""]- terminals
[]- cursor
5- output
" a b"- prefix
null- tokenStart
4- tokenEnd
5- replacementEnd
-1- phase
"emit"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
[]- sentence
" a b "- paths
[""]- terminals
[]- cursor
6- output
" a b "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Return the documented operation outcomes, unique found words, or exact replacement text.
Trie path displays are logical views. Board-path visited state and terminal flags have different lifetimes; no caller-owned input is mutated.
- result
" a b "
All-space sentence has no tokens
Input: {"dictionary":["a"],"sentence":" "} · Exact replacement text: " "
Step 1 of 5: Build root terminals without changing dictionary order.
The root path is not terminal because empty roots are rejected. The first terminal encountered on a token path is the shortest matching root.
Phase: initial.
Trie paths — sorted logical display
- (root / empty path)prefix path only
- aterminal word
Input with each space shown as ·: ···
Output so far with spaces shown as ·: (empty)
Original scan boundary: 0. Token span: none. Replacement end: no terminal selected.
Token bounds are half-open. The original scan already reaches the whole token end before the separate trie probe runs. The first terminal gives the shortest complete root; its discarded suffix is not rescanned. The · symbols are display markers only; Java returns actual unchanged space characters.
Path cards represent shared dictionary prefixes, not board cells or dictionary occurrence order. Complete exact state and equivalent static steps remain available below.
| Variable | Value |
|---|---|
| dictionary | ["a"] |
| sentence | " " |
| paths | ["","a"] |
| terminals | ["a"] |
| cursor | 0 |
| output | "" |
| prefix | null |
| tokenStart | null |
| tokenEnd | null |
| replacementEnd | -1 |
| phase | "initial" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Node { final Node[] children = new Node[26]; boolean terminal; } 4 private static void validate(String[] dictionary, String sentence) { 5 Objects.requireNonNull(dictionary,"dictionary"); Objects.requireNonNull(sentence,"sentence"); 6 for (String word : dictionary) { 7 Objects.requireNonNull(word,"root"); 8 if (word.isEmpty()) throw new IllegalArgumentException("empty root"); 9 for (int i=0;i<word.length();i++) if (word.charAt(i) < 'a' || word.charAt(i) > 'z') throw new IllegalArgumentException("invalid root letter"); 10 } 11 for (int i=0;i<sentence.length();i++) { char c=sentence.charAt(i); if (c != ' ' && (c < 'a' || c > 'z')) throw new IllegalArgumentException("invalid sentence character"); } 12 } 13 public static String replace(String[] dictionary, String sentence) { 14 validate(dictionary,sentence); 15 Node root = new Node(); 16 for (String word : dictionary) { 17 Node node = root; 18 for (int i=0;i<word.length();i++) { 19 int slot=word.charAt(i)-'a'; 20 if (node.children[slot] == null) node.children[slot] = new Node(); 21 node=node.children[slot]; 22 } 23 node.terminal=true; 24 } 25 StringBuilder output = new StringBuilder(); 26 for (int i=0;i<sentence.length();) { 27 if (sentence.charAt(i) == ' ') { output.append(' '); i++; continue; } 28 int start=i; 29 while (i<sentence.length() && sentence.charAt(i) != ' ') i++; 30 Node node=root; int replacementEnd=-1; 31 for (int j=start;j<i;j++) { 32 node=node.children[sentence.charAt(j)-'a']; 33 if (node == null) break; 34 if (node.terminal) { replacementEnd=j+1; break; } 35 } 36 output.append(sentence,start,replacementEnd < 0 ? i : replacementEnd); 37 } 38 return output.toString(); 39 } 40 public static String baseline(String[] dictionary, String sentence) { 41 validate(dictionary,sentence); 42 StringBuilder output = new StringBuilder(); 43 for (int i=0;i<sentence.length();) { 44 if (sentence.charAt(i) == ' ') { output.append(' '); i++; continue; } 45 int start=i; while(i<sentence.length() && sentence.charAt(i) != ' ') i++; 46 int length=i-start; 47 for (String root : dictionary) if (root.length() <= length && sentence.startsWith(root,start)) length=root.length(); 48 output.append(sentence,start,start+length); 49 } 50 return output.toString(); 51 } 52 } 53
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Build root terminals without changing dictionary order.
The root path is not terminal because empty roots are rejected. The first terminal encountered on a token path is the shortest matching root.
- dictionary
["a"]- sentence
" "- paths
["","a"]- terminals
["a"]- cursor
0- output
""- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"initial"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["a"]- sentence
" "- paths
["","a"]- terminals
["a"]- cursor
1- output
" "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["a"]- sentence
" "- paths
["","a"]- terminals
["a"]- cursor
2- output
" "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Copy one original ASCII space exactly.
Leading, repeated and trailing spaces are copied rather than normalized by token joining.
- dictionary
["a"]- sentence
" "- paths
["","a"]- terminals
["a"]- cursor
3- output
" "- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"space"
- Return the documented operation outcomes, unique found words, or exact replacement text.
Trie path displays are logical views. Board-path visited state and terminal flags have different lifetimes; no caller-owned input is mutated.
- result
" "
Empty sentence
Input: {"dictionary":["a"],"sentence":""} · Exact replacement text: ""
Step 1 of 2: Build root terminals without changing dictionary order.
The root path is not terminal because empty roots are rejected. The first terminal encountered on a token path is the shortest matching root.
Phase: initial.
Trie paths — sorted logical display
- (root / empty path)prefix path only
- aterminal word
Input with each space shown as ·: (empty)
Output so far with spaces shown as ·: (empty)
Original scan boundary: 0. Token span: none. Replacement end: no terminal selected.
Token bounds are half-open. The original scan already reaches the whole token end before the separate trie probe runs. The first terminal gives the shortest complete root; its discarded suffix is not rescanned. The · symbols are display markers only; Java returns actual unchanged space characters.
Path cards represent shared dictionary prefixes, not board cells or dictionary occurrence order. Complete exact state and equivalent static steps remain available below.
| Variable | Value |
|---|---|
| dictionary | ["a"] |
| sentence | "" |
| paths | ["","a"] |
| terminals | ["a"] |
| cursor | 0 |
| output | "" |
| prefix | null |
| tokenStart | null |
| tokenEnd | null |
| replacementEnd | -1 |
| phase | "initial" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Node { final Node[] children = new Node[26]; boolean terminal; } 4 private static void validate(String[] dictionary, String sentence) { 5 Objects.requireNonNull(dictionary,"dictionary"); Objects.requireNonNull(sentence,"sentence"); 6 for (String word : dictionary) { 7 Objects.requireNonNull(word,"root"); 8 if (word.isEmpty()) throw new IllegalArgumentException("empty root"); 9 for (int i=0;i<word.length();i++) if (word.charAt(i) < 'a' || word.charAt(i) > 'z') throw new IllegalArgumentException("invalid root letter"); 10 } 11 for (int i=0;i<sentence.length();i++) { char c=sentence.charAt(i); if (c != ' ' && (c < 'a' || c > 'z')) throw new IllegalArgumentException("invalid sentence character"); } 12 } 13 public static String replace(String[] dictionary, String sentence) { 14 validate(dictionary,sentence); 15 Node root = new Node(); 16 for (String word : dictionary) { 17 Node node = root; 18 for (int i=0;i<word.length();i++) { 19 int slot=word.charAt(i)-'a'; 20 if (node.children[slot] == null) node.children[slot] = new Node(); 21 node=node.children[slot]; 22 } 23 node.terminal=true; 24 } 25 StringBuilder output = new StringBuilder(); 26 for (int i=0;i<sentence.length();) { 27 if (sentence.charAt(i) == ' ') { output.append(' '); i++; continue; } 28 int start=i; 29 while (i<sentence.length() && sentence.charAt(i) != ' ') i++; 30 Node node=root; int replacementEnd=-1; 31 for (int j=start;j<i;j++) { 32 node=node.children[sentence.charAt(j)-'a']; 33 if (node == null) break; 34 if (node.terminal) { replacementEnd=j+1; break; } 35 } 36 output.append(sentence,start,replacementEnd < 0 ? i : replacementEnd); 37 } 38 return output.toString(); 39 } 40 public static String baseline(String[] dictionary, String sentence) { 41 validate(dictionary,sentence); 42 StringBuilder output = new StringBuilder(); 43 for (int i=0;i<sentence.length();) { 44 if (sentence.charAt(i) == ' ') { output.append(' '); i++; continue; } 45 int start=i; while(i<sentence.length() && sentence.charAt(i) != ' ') i++; 46 int length=i-start; 47 for (String root : dictionary) if (root.length() <= length && sentence.startsWith(root,start)) length=root.length(); 48 output.append(sentence,start,start+length); 49 } 50 return output.toString(); 51 } 52 } 53
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Build root terminals without changing dictionary order.
The root path is not terminal because empty roots are rejected. The first terminal encountered on a token path is the shortest matching root.
- dictionary
["a"]- sentence
""- paths
["","a"]- terminals
["a"]- cursor
0- output
""- prefix
null- tokenStart
null- tokenEnd
null- replacementEnd
-1- phase
"initial"
- Return the documented operation outcomes, unique found words, or exact replacement text.
Trie path displays are logical views. Board-path visited state and terminal flags have different lifetimes; no caller-owned input is mutated.
- result
""
Test the contract
Input:
Empty dictionary
Output:sentence unchanged in contentNo replacement roots.
Input:
Empty or all-space sentence
Output:same contentNo invented tokens or dropped spaces.
Input:
Short and long overlapping roots in reverse insertion order
Output:shortest matching rootOrdering independent.
Input:
10,000-character root and longer token
Output:exact long root spanIterative trie walk.
Input:
100,000-character unmatched token
Output:unchanged tokenNo quadratic substring-oracle work in the large-path test.
Common mistakes and counterexamples
Choose the longest matching root
Counterexample: cattle has roots c,cat,cattle but must become c.
Stop at the first terminal depth.
Replace an internal nonterminal prefix
Counterexample: Adding cattle alone must not turn cat into a root.
Require the terminal marker.
Split on generic whitespace and join with one space
Counterexample: Leading, double and trailing spaces would change.
Copy each literal space and scan maximal letter spans.
Resume at the replacement’s end
Counterexample: Removing attle from cattle must not process attle as another token.
Keep the outer cursor at the original token end.
Follow-ups
Preserve arbitrary Unicode whitespace.
Define token boundaries and normalization deliberately, including surrogate pairs and locale-sensitive casing. A 26-child ASCII array and char-based space test do not implement that broader contract.
Choose the longest root instead.
Continue after terminal nodes while retaining the latest terminal span, stopping only at a missing edge or token end. The current first-terminal proof must change.
Reuse one dictionary for many sentences.
Expose a built immutable trie with read-only replacement calls. Specify thread safety and separate O(S) preprocessing from O(n) per-sentence work; updates need a different ownership policy.
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 · 185/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.