Replace Words

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 length.

Return the sentence after the replacement.

LeetCode Problem - 648

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        // Split the sentence into an array of words
        String[] sentenceArray = sentence.split(" ");
        // Initialize a map to store the shortest replacement roots for each word in the sentence
        Map<String, String> mp = new HashMap<>();
        // Initialize a StringBuilder to build the final sentence
        StringBuilder sb = new StringBuilder();

        // Iterate over each word in the dictionary
        for (String currentDictionaryWord : dictionary) {
            // Iterate over each word in the sentence
            for (String currentSentenceWord : sentenceArray) {
                // Check if the current sentence word starts with the current dictionary word
                if (currentSentenceWord.startsWith(currentDictionaryWord)) {
                    // If the map already contains this sentence word, compare lengths of roots
                    if (mp.containsKey(currentSentenceWord)) {
                        String previousValue = mp.get(currentSentenceWord);
                        int previousKeyLength = previousValue.length();
                        int currentKeyLength = currentDictionaryWord.length();
                        // Update the map with the shorter root
                        if (currentKeyLength < previousKeyLength) {
                            mp.put(currentSentenceWord, currentDictionaryWord);
                        } else {
                            mp.put(currentSentenceWord, previousValue);
                        }
                    } else {
                        // If the map does not contain this sentence word, add it
                        mp.put(currentSentenceWord, currentDictionaryWord);
                    }
                }
            }
        }

        // Iterate over each word in the sentence array
        for (String str : sentenceArray) {
            // If the map contains a replacement root for this word, use it
            if (mp.containsKey(str)) {
                String value = mp.get(str);
                sb.append(value).append(" ");
            } else {
                // Otherwise, use the original word
                sb.append(str).append(" ");
            }
        }

        // Return the final sentence, trimmed to remove any trailing spaces
        return sb.toString().trim();
    }
}