896. Root Replacements
A telegram operator shortens messages by swapping each word for its shortest known stem. You receive a list of stems roots and a message sentence made of lowercase words separated by single spaces.
Replace every word of sentence by the shortest stem in roots that is a prefix of that word. If no stem is a prefix of the word, keep the word unchanged. Empty strings inside roots are ignored. The sentence is split at every single space character, so consecutive, leading or trailing spaces produce empty words that stay empty; join the words back with single spaces and return the result. Aim for time linear in the total input size.
Example 1
- Input:
- roots = ["gl","glob","tur"]sentence = "global turbine glider turtle"
- Output:
- "gl tur gl tur"
- Explanation:
The stems
glandturare the shortest matching prefixes of all four words, so every word collapses to its stem.
Example 2
- Input:
- roots = ["ka","kay"], sentence = "kayak kite kayo"
- Output:
- "ka kite ka"
- Explanation:
kayakandkayoboth start withka(shorter thankay);kitehas no stem and stays.
Example 3
- Input:
- roots = ["ob"], sentence = " oboe obey "
- Output:
- " ob ob "
- Explanation:
Spaces are kept exactly as given, so the leading space, the double space and the trailing space all survive.
Constraints
0 ≤ roots.length ≤ 5000, 0 ≤ roots[i].length ≤ 30
0 ≤ sentence.length ≤ 105
All characters are lowercase letters; sentence may also contain spaces.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(R + S)
- Space
- O(R)