648. Replace Words


In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can 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"

Note:

  1. The input will only have lower-case letters.
  2. 1 <= dict words number <= 1000
  3. 1 <= sentence words number <= 1000
  4. 1 <= root length <= 100
  5. 1 <= sentence words length <= 1000


Approach #1: Prefix Hash [Accepted]

Intuition

For each word in the sentence, we'll look at successive prefixes and see if we saw them before.

Algorithm

Store all the roots in a Set 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: where is the length of the -th word. We might check every prefix, the -th of which is work.

  • Space Complexity: where is the length of our sentence; the space used by rootset.

Approach #2: Trie [Accepted]

Intuition and Algorithm

Put all the roots in a trie (prefix tree). Then for any query word, we can find the smallest root that was a prefix in linear time.

Complexity Analysis

  • Time Complexity: where is the length of the sentence. Every query of a word is in linear time.

  • Space Complexity: , the size of our trie.

Analysis written by: @awice.

Submit Solution