medium

Replace Words

Swap each word in a sentence for the shortest dictionary root that starts it, found by walking the word down a trie of roots.

1. Define the problem

Replace Words

In English, some words are built by sticking extra letters onto a shorter word. The shorter word is called the root . For example "cat" is the root of "cattle". You are given a list of roots and a sentence. Replace every word in the sentence with the shortest root that starts it . If no root starts the word, leave the word alone. Put every root into a trie. Then, for each word in the sentence, walk its letters down the trie and stop at the first end-of-word marker you hit — because you walk from the front, the first marker is always the shortest matching root. Words in the sentence are separated by exactly one space, and the answer is those words joined back together with single spaces.

Constraints

  • 1 ≤ dictionary.length ≤ 1000
  • 1 ≤ dictionaryi.length ≤ 100
  • 1 ≤ sentence.length ≤ 106
  • The sentence has words separated by single spaces, with no leading or trailing space

Example

Inputdictionary = ["cat", "bat", "rat"], sentence = "the cattle was rattled by the battery"
Output"the cat was rat by the bat"

Explanation "cattle" starts with the root "cat", "rattled" starts with "rat", and "battery" starts with "bat". The words "the", "was" and "by" start with no root, so they are kept as they are.

2. Know the words first

In plain terms

Root (word root)
A shorter word that another word is built from. Here it just means a stored word that appears at the very start of a longer word.
Trie
A tree of letters where each stored word is a path down from the top. Words sharing a beginning share a path.
End-of-word marker
A true/false flag on a node meaning "one of the stored words finishes right here".
3. Visualize the solution

Walking "cattle" down the trie of roots until a root ends

Walking "cattle" down the trie of roots until a root ends
Statusinit

The roots "cat", "bat" and "rat" are stored in the trie; now handle the word "cattle".

What happens in this step

dictionary = ["cat", "bat", "rat"]
word = 'cattle'
node = root, prefix = ''

The trie has three separate branches, one starting with c, one with b, one with r.
Step 1 of 6

Steps to visualize

  1. The row of cells is the word being replaced, one cell per letter.
  2. The value shows what the trie node for that letter looks like: "node" means the path continues, "root!" means a stored root ends there, "skip" means the letter was never reached.
  3. The walk stops at the very first "root!" because walking from the front means the first match is always the shortest one.
  4. If a letter has no link in the trie, the word has no root and is kept unchanged.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Walking "cattle" down the trie of roots until a root ends
Statusinit

The roots "cat", "bat" and "rat" are stored in the trie; now handle the word "cattle".

What happens in this step

dictionary = ["cat", "bat", "rat"]
word = 'cattle'
node = root, prefix = ''

The trie has three separate branches, one starting with c, one with b, one with r.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function replaceWords(dictionary, sentence) {
  class TrieNode {
    constructor() {
      this.children = {};
      this.isEnd = false;
    }
  }

  const root = new TrieNode();

  for (const word of dictionary) {
    let node = root;
    for (const ch of word) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
      }
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  const shortestRoot = (word) => {
    let node = root;
    let prefix = '';

    for (const ch of word) {
      node = node.children[ch];
      if (!node) {
        return word;
      }
      prefix += ch;
      if (node.isEnd) {
        return prefix;
      }
    }

    return word;
  };

  return sentence.split(' ').map((word) => shortestRoot(word)).join(' ');
}
Time
O(total letters in the roots plus total letters in the sentence)
Space
O(total letters in the roots)
6. Test cases

Test cases

InputExpectedCovers
dictionary = ["cat", "bat", "rat"], sentence = "the cattle was rattled by the battery""the cat was rat by the bat"example from the docstring
dictionary = ["a", "aa", "aaa"], sentence = "aaaa aaa aa a""a a a a"several roots start the same word, the shortest must win
dictionary = ["x", "y"], sentence = "hello there""hello there"no root starts any word, so the sentence is unchanged
dictionary = [], sentence = "keep every word""keep every word"an empty root list leaves everything alone
dictionary = ["cat"], sentence = "cat""cat"a word that is exactly a root replaces itself
dictionary = ["catt"], sentence = "cat""cat"a root longer than the word cannot match

Keep reading