LESSON 466 OF 635 · TRIES

Replace Words in Java

Practice O(S)

You get an array of strings roots and a string sentence. The words of sentence are separated by single spaces.

Return the sentence after replacing each word that starts with a root by that root.

If a word starts with more than one root, use the shortest one. A root can also be the whole word. Words that start with no root stay as they are.

Example 1:

Input: roots = ["sun","snow"], sentence = "sunny days and snowy nights"
Output: "sun days and snow nights"
Explanation: "sunny" starts with "sun".
"snowy" starts with "snow".
The other words start with no root.

Example 2:

Input: roots = ["book","bookworm"], sentence = "bookworms read books"
Output: "book read book"
Explanation: "bookworms" starts with "book" and with "bookworm".
The shorter root, "book", wins.
"books" becomes "book" too.

Example 3:

Input: roots = ["moon"], sentence = "mo moonlight moon"
Output: "mo moon moon"
Explanation: "mo" is shorter than the root, so it stays.
"moonlight" starts with "moon".
The last word is the root itself.

Constraints:

1 to 1,000 roots.
Each root has 1 to 100 letters.
sentence has 1 to 10,000 words.
Each word has 1 to 100 letters.
Every letter is from a to z.
One space separates each two words.
There are no spaces at the start or the end.

Note:

Your solution should run in O(S) time. S is the total number of letters in roots and sentence.

Put the roots in a trie, and mark the node where each root ends.

For each word, walk down the trie letter by letter. The first node where a root ends gives the shortest root. If the trie has no path for the next letter, or the word ends first, keep the word.

Building the trie visits each letter of the roots once. Each walk is at most as long as its word: O(S) time.
The trie and the new sentence take O(S) extra space.

STEP 1 OF 18

Guided

Ctrl + Enter to check