Share Feedback
Help us improve this platform
Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.
Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was meowed by the ratings"
Output: "the cat was meowed by the rat"
Topics: trie, hash-map
Asked by: Uber, Amazon, Google
Time complexity: O(Sum of words). Space complexity: O(Trie size).