Typorithm · medium

Replace Words

replace-wordstriesshortest-rootprefix-matchapplication

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Replace Words

Tries

Index roots in a trie, then for each word walk until the first isEnd node — the shortest matching root — else keep the word.

Given dictionary roots, replace each word with the shortest root that is a prefix of it.

Insert every root into a trie, then walk each word character by character.

The first node flagged isEnd is the shortest root; if the walk dead-ends, keep the original word.

Trie holds all roots.

Return at the first isEnd node.

Fall back to the whole word.

function replaceWords(roots, sentence) {
  const trie = new Trie();
  for (const root of roots) {
    trie.insert(root);
  }

  function rootOf(word) {
    let node = trie;
    let prefix = "";
    for (const ch of word) {
      if (!node.children.has(ch)) {
        break;
      }
      prefix += ch;
      node = node.children.get(ch);
      if (node.isEnd) {
        return prefix;
      }
    }
    return word;
  }

  return sentence.split(" ").map(rootOf).join(" ");
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Index the roots

Store all dictionary roots in the trie.

trie.insert(root)

2. Grow the prefix

Extend the candidate root one character at a time.

prefix += ch

3. First root wins

Stop at the first complete root — it is the shortest.

if (node.isEnd) {
        return prefix;
      }

4. No root

Keep the original word when no root applies.

return word

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.