Leetcode•Mar 25, 2026

Replace Words

Hazrat Ali

Leetcode

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.

 

Example 1:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Example 2:

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"

Solution
class TrieNode {
    constructor() {
        this.children = {};
        this.isEnd = false;
    }
}

var replaceWords = function(dictionary, sentence) {

    let root = new TrieNode();

    for (let word of dictionary) {
        let node = root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEnd = true;
    }

    function findRoot(word) {
        let node = root;
        let prefix = "";

        for (let char of word) {
            if (!node.children[char]) return word;
            prefix += char;
            node = node.children[char];

            if (node.isEnd) return prefix;
        }

        return word;
    }

    return sentence
        .split(" ")
        .map(word => findRoot(word))
        .join(" ");
};


Comments