Shorten Words to Their Roots

Medium

You have a dictionary of roots roots and a text text whose words are separated by single spaces. Whenever a word of the text starts with a root from the dictionary, replace the whole word with that root. If several roots fit, use the shortest one. Words that start with no root stay unchanged. Return the resulting text, keeping the word order and the single spaces between words.

Example 1

roots=['sun', 'moon', 'star'], text='sunflowers bloom under starlight and moonbeams' → 'sun bloom under star and moon'

"sunflowers" starts with the root sun, "starlight" with star and "moonbeams" with moon. The other words start with no root and stay as they are.

Example 2

roots=['pre', 'p', 'pref'], text='prefix press apple' → 'p p apple'

"prefix" and "press" start with several roots at once, so the shortest one, p, wins.

Example 3

roots=['rain'], text='rain rainbow train' → 'rain rain train'

The root must sit at the very start of the word: "train" contains rain but does not begin with it.

Constraints

1 ≤ len(roots) ≤ 10⁴
1 ≤ len(roots[i]) ≤ 100
1 ≤ len(text) ≤ 10⁶
The text has 1 to 10⁵ words, each 1 to 1000 characters long
Words are separated by exactly one space, with no leading or trailing spaces
Roots and words consist of lowercase English letters only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Trie Array Hash Table String

Similar problems

Split Into Dictionary Words Medium Highlight Search Hits Medium Most Searched Words Medium Word Grown Letter by Letter Medium Highlight Search Terms Medium

Input

roots=['sun', 'moon', 'star'], text='sunflowers bloom under starlight and moonbeams'

Expected

'sun bloom under star and moon'

Run checks the first 3 tests in your browser. Submit checks all 185 tests on the server, hidden ones included.