Skip to content
MediumStringsAI interview only

Replace Words

Asked atamazongooglemicrosoftuber

01 · Problem

You have a dictionary of roots. Any word that begins with a root is a derivative of that root.

Given a sentence of words separated by single spaces, replace every derivative with the root it begins with. If a word begins with several roots, use the shortest one. A word that begins with no root is left as is (a word equal to a root also stays the same).

Return the resulting sentence, with words still separated by single spaces.

02 · Examples

Example 01
Input
dictionary = ["go","gold","sun"], sentence = "golden sunsets go by"
Output
"go sun go by"

"golden" has roots "go" and "gold"; the shorter "go" wins. "sunsets" becomes "sun", "go" is already a root, and "by" has no root so it stays.

Example 02
Input
dictionary = ["ab","x"], sentence = "abc xyz yes"
Output
"ab x yes"

"abc" starts with "ab" and "xyz" starts with "x". "yes" matches no root and is unchanged.

Example 03
Input
dictionary = ["re","rep","pre"], sentence = "repeat the prefix test"
Output
"re the pre test"

"repeat" matches both "re" and "rep"; the shortest root "re" is used. "prefix" becomes "pre". The other words have no root.

03 · Constraints

  • 011 <= dictionary.length <= 1000
  • 021 <= dictionary[i].length <= 100
  • 031 <= sentence.length <= 105
  • 04dictionary[i] and the words of sentence consist of lowercase English letters
  • 05sentence has no leading or trailing spaces and words are separated by exactly one space

04 · Optimal complexity

Time
O(N + S)
Space
O(N)
05 · Two ways to work on it

Practice it alone or rehearse it as an interview.

Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.

Start a voice interview on this problem