Asked at

Replace Words

Medium
VerifiedTrieHash MapString~25 min

Each word in sentence may have a root in dictionary. Replace each word with the shortest dictionary root that is a prefix of it.

If no root applies, keep the word. Build a trie (or set) of roots and match the shortest prefix per word.

The input arrives as a single object { dictionary, sentence }. Return the rebuilt sentence.

Examples

in{ dictionary: ["cat", "bat", "rat"], sentence: "the cattle was rattled by the battery" }
out"the cat was rat by the bat"

Each word is replaced by the shortest root that prefixes it.

in{ dictionary: ["a", "b", "c"], sentence: "aadsfasf absbs bbab cadsfafs" }
out"a a b c"

Single-letter roots match the start of each word.

Constraints

  • 1 ≤ dictionary.length ≤ 1000
  • 1 ≤ sentence words ≤ 1000
  • All inputs consist of lowercase letters; words are space-separated.

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.