Replace Words

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:

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

Solution

public class Solution {
    public String replaceWords(List<String> dict, String sentence) {
        dict.sort((a, b) -> a.length() - b.length());
        String[] words = sentence.split("\\s+");
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            for (String root: dict) {
                if (word.startsWith(root)) {
                    words[i] = root;
                    break; //Needs break here cause we just want to replace with the shortest root;
                }
            }
        }
        return String.join(" ", words);
    }
}

Analysis

We first sort the given dict with length
Then we loop through each word from the given sentence
We use another loop to find the shortest root and replace the words[i] with that root
At the end, we use String.join(" ", array) to construct required sentence