Replace Words

MediumStringstrie

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a list of **roots** dictionary and a sentence of lowercase words separated by single spaces. Replace every word in the sentence that begins with some root by that root. If several roots are prefixes of the same word, use the **shortest** one. Words with no matching root stay unchanged. A root may equal the whole word. Return the resulting sentence, still separated by single spaces.

Examples

Input: dictionary = ["re","rest","un"], sentence = "unrest restarts the reader"
Output: "un re the re"
"unrest" starts with "un"; "restarts" starts with both "re" and "rest", and the shorter wins; "the" has no root.
Input: dictionary = ["ab","abc"], sentence = "abcd xab ab"
Output: "ab xab ab"
"xab" contains "ab" but does not start with it, so it is kept.

Constraints

  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 100
  • 1 <= sentence.length <= 10^6
  • sentence has no leading or trailing spaces and words are separated by exactly one space
  • All strings contain only lowercase English letters (plus spaces in sentence)

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More trie problems