LeetCode 648 Replace Words - Problem Statement

Given a dictionary of roots and a sentence, replace each word with its shortest root.

A root is a prefix. If a word starts with a root, replace the entire word with that root.

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

• "cattle" starts with "cat" → replace with "cat"
• "rattled" starts with "rat" → replace with "rat"
• "battery" starts with "bat" → replace with "bat"
• "the", "was", "by" have no root → keep them

Result: "the cat was rat by the bat".

Constraints: $1 \le$ dictionary size $\le 1000$. $1 \le$ sentence length $\le 10^6$.