Replace Words Problem

Replace Words Problem — ExecCode Medium DSA Practice

Solve the Replace Words problem on ExecCode. Free online medium DSA practice in Arrays - Logic Building. Write and run code in Java, C++, Python — no signup required to run.

Problem description

In English, a "root" can have many "successor" words formed by appending letters. Given a dictionary of roots and a sentence, replace every word in the sentence with its shortest matching root, if one exists. If a word has multiple roots that match as a prefix, replace it with the root of the shortest length; words with no matching root stay unchanged.

Examples

Input dictionary = ["cat", "bat", "rat"], sentence = "the cattle was rattled by the battery"; Output "the cat was rat by the bat". Input dictionary = ["a", "b", "c"], sentence = "aadsfasf absbs bbab cccb"; Output "a a b c". Input dictionary = ["cat"], sentence = "cats and dogs"; Output "cat and dogs"

Constraints

1 <= dictionary.length <= 1000 1 <= dictionary[i].length <= 100 1 <= sentence.length <= 10^6 All strings consist of lowercase English letters and single spaces separate sentence words

Practice Replace Words free on ExecCode. Browse DSA problems, topic map, and placement guides.