In English, we have a concept calledroot, which can be followed by some other words to form another longer word - let's call this wordsuccessor. For example, the rootan, followed byother, which can form another wordanother.
Now, given a dictionary consisting of many roots and a sentence. You need to replace all thesuccessorin the sentence with therootforming it. If asuccessorhas manyrootscan form it, replace it with the root with the shortest length.
You need to output the sentence after the replacement.
Example 1:
Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"