A dictionary contains roots such as "cat". In a sentence of space-separated words, replace every word that starts with a root by the shortest root that is a prefix of it. A word that starts with no root stays as it is. Return the new sentence.
replaceWords(["cat", "bat", "rat"], "the cattle was rattled by the battery") is "the cat was rat by the bat"- When several roots fit (
"a" and "ab" for "abc"), the shortest wins - Aim for time proportional to the total length of the roots plus the sentence, not roots times words