LeetCode #648 Replace Words

Medium

Problem

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

Solution

Use a trie to save each root and replace each word in sentence by searching root in this trie.

Complexity

We first build this trie by iterating each root in dict, so it will takes O(m) time if m denotes to sum of letters of all roots in dict. Then, we will map every word of original sentence to be its root by calling replace function. This behavior also takes O(n) time if n denotes to length of entire sentence. Therefore, total time complexity will be O(m+n).

For space complexity, there is a trie for saving each root so it needs O(m) extra space.