How do you approach Replace Words With Roots?

Insert every root into a trie, marking the node that ends a root.

What is the time complexity of Replace Words With Roots?

Time complexity: O(total dictionary characters + total sentence characters). Space complexity: O(total dictionary characters).

What are common mistakes on Replace Words With Roots?

Leaving out the end-of-word flag, so a lookup reports words that were never inserted. Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest. Not handling the empty string, which is a valid prefix of everything.

gitGood.dev

← Back to problems

Replace Words With Roots

MediumData Structures

Description

In English, a derivative is formed by adding a suffix to a root: help is a root of helpful.

Given a dictionary of roots and a sentence of space-separated words, replace every word in the sentence with the shortest root that is a prefix of it. If no root applies, leave the word unchanged.

Return the resulting sentence.

Example 1

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"

Output: "the cat was rat by the bat"

Example 2

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"

Output: "a a b c"

Example 3

Input: dictionary = ["catt","cat"], sentence = "the cattle"

Output: "the cat"

Constraints

- 0 <= dictionary.length <= 1000 - 1 <= root length <= 100 - 1 <= sentence words <= 1000 - All lowercase English letters, words separated by single spaces.

Replace Words With Roots: approach, complexity and pitfalls

A medium trie problem, graded against 6 test cases (3 of them hidden).

The pattern: Trie

A prefix tree for fast string lookup by shared prefix.

Reach for it when you see: Many words, repeated prefix queries, autocomplete, or word-search over a grid.

If you are stuck

Show the 3-step hint ladder

Insert every root into a trie, marking the node that ends a root.
For each word, walk the trie character by character and STOP at the first node marked as a root end - that is the shortest root by construction.
If you fall off the trie before hitting a root marker, the word has no root; emit it unchanged.

The optimal approach

Show the approach: Stop at the first marker and shortest comes for free

Build a trie of the roots, marking terminal nodes. Then for each word, walk down from the root one character at a time and stop the moment you stand on a marked node - emitting the characters consumed so far.

That early stop is the entire solution to the "shortest root" requirement. Because you descend in increasing length order, the first marker you meet is necessarily the shortest matching root, so `["catt", "cat"]` against `cattle` yields `cat` without any comparison of candidate lengths. Sorting the dictionary or collecting all matches and taking the minimum is wasted work.

If the walk falls off the trie (no child for the next character) without ever hitting a marker, no root is a prefix of this word, so it passes through untouched.

Compared with checking every root against every word - O(words x roots x length) - the trie makes each word cost only its own length.

Time: O(total dictionary characters + total sentence characters)
Space: O(total dictionary characters)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.

Common Trie mistakes

These apply to the pattern as a whole, not just this problem.

Leaving out the end-of-word flag, so a lookup reports words that were never inserted.
Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest.
Not handling the empty string, which is a valid prefix of everything.