Replace Words In Sentence With Shortest Root
Replace words in sentence with shortest root from dictionary using Trie data structure for efficient lookup.
648. Replace Words Difficulty: Medium Topics: Array, Hash Table, String, Trie In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful". 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 le...