Shortest Root Substitution
MediumTries & Strings
Problem
A text compressor has a list of roots. Every word in a sentence that starts with one or more roots is replaced by the shortest of those roots; words that start with no root stay as they are.
The sentence is lowercase words separated by single spaces. Return the compressed sentence.
Example 1
- Input:
- roots = ["un","under","re"], sentence = "understand the rerun results"
- Output:
- "un the re re"
"understand" starts with both "un" and "under"; the shorter one wins. "the" matches nothing.
Example 2
- Input:
- roots = ["b","ba"], sentence = "banana bandana cab"
- Output:
- "b b cab"
"cab" contains "b" but does not start with it.
Constraints
- 1 ≤ roots.length ≤ 1000
- 1 ≤ roots[i].length ≤ 100
- 1 ≤ sentence.length ≤ 10^6
- Lowercase letters and single spaces only; no leading or trailing space.
Hint
Show the first hint
For each word you only care about the first root you meet while reading it from the left.
Walkthrough
How to approach it
01Clarify before coding
- If several roots match, which one? The shortest.
- Must the root be a prefix, or can it appear anywhere? Only a prefix of the word.
- Can a word be shorter than every root? Yes; it is left unchanged.
02Brute force
For each word, test every root with startsWith and keep the shortest match.
Cost: O(W·R·L) for W words, R roots of length L: up to 10^5 · 10^3 · 100 comparisons.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.