function Trie() {
    this.children = {};
    this.isLeaf = null;

    this.insert = function(str, index) {
        if (!str.length) {
            this.isLeaf = index;
            return;
        }
        if (this.children[str[0]]) {
            this.children[str[0]].insert(str.slice(1), index);
        } else {
            const trie = new Trie();
            trie.insert(str.slice(1), index);
            this.children[str[0]] = trie;
        }
    };

    this.getIndex = function(str) {
        if (this.isLeaf != null) {
            return this.isLeaf;
        }
        if (!str.length || !this.children[str[0]]) {
            return null;
        }

        return this.children[str[0]].getIndex(str.slice(1));
    };
};

/**
 * @param {string[]} dict
 * @param {string} sentence
 * @return {string}
 */
var replaceWords = function(dict, sentence) {
    const trie = new Trie();
    for (let i=0; i<dict.length; ++i) {
        trie.insert(dict[i], i);
    }
    const words = sentence.split(' ');
    for (let i=0; i<words.length; ++i) {
        const dictIndex = trie.getIndex(words[i]);
        if (dictIndex != null) {
            words[i] = dict[dictIndex];
        }
    }
    return words.join(' ');
};