Photo by Joshua Hoehne on Unsplash

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 successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

Constraints:

  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] consists of only lower-case letters.
  • 1 <= sentence.length <= 10^6
  • sentence consists of only lower-case letters and spaces.
  • The number of words in sentence is in the range [1, 1000]
  • The length of each word in sentence is in the range [1, 1000]
  • Each two consecutive words in sentence will be separated by exactly one space.
  • sentence does not have leading or trailing spaces.

Algorithm

Store all the roots in a HashSet data structure. Then for each word, look at successive prefixes of that word. If you find a prefix that is a root, replace the word with that prefix. Otherwise, the prefix will just be the word itself, and we should add that to the final sentence answer.

Complexity Analysis

  • Time Complexity : O(∑wi2​) where wi​ is the length of the i-th word. We might check every prefix, the i-th of which is O(wi2​) work.
  • Space Complexity : O(N) where NN is the length of our sentence; the space used by rootset.

Full Stack Programmer, love to solve problem’s during free time.