Code Implementation

class Solution:
    def replaceWords(self, dictionary, sentence):
        trie = {}
        for root in dictionary:
            node = trie
            for char in root:
                if char not in node:
                    node[char] = {}
                node = node[char]
            node['#'] = True  # End of root marker

        def replace(word):
            node = trie
            prefix = ''
            for char in word:
                if char not in node:
                    break
                prefix += char
                node = node[char]
                if '#' in node:
                    return prefix
            return word

        return ' '.join(replace(word) for word in sentence.split())
      

class Solution {
public:
    struct TrieNode {
        bool isEnd;
        unordered_map<char, TrieNode*> children;
        TrieNode() : isEnd(false) {}
    };

    void insert(TrieNode* root, const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c))
                node->children[c] = new TrieNode();
            node = node->children[c];
        }
        node->isEnd = true;
    }

    string replace(const string& word, TrieNode* root) {
        TrieNode* node = root;
        string prefix;
        for (char c : word) {
            if (!node->children.count(c))
                break;
            prefix += c;
            node = node->children[c];
            if (node->isEnd)
                return prefix;
        }
        return word;
    }

    string replaceWords(vector<string>& dictionary, string sentence) {
        TrieNode* root = new TrieNode();
        for (const string& word : dictionary)
            insert(root, word);

        istringstream iss(sentence);
        string word, result;
        while (iss >> word) {
            if (!result.empty()) result += " ";
            result += replace(word, root);
        }
        return result;
    }
};
      

class Solution {
    static class TrieNode {
        boolean isEnd;
        Map<Character, TrieNode> children = new HashMap<>();
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        TrieNode root = new TrieNode();
        for (String word : dictionary) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node = node.children.computeIfAbsent(c, k -> new TrieNode());
            }
            node.isEnd = true;
        }

        StringBuilder sb = new StringBuilder();
        for (String word : sentence.split(" ")) {
            TrieNode node = root;
            StringBuilder prefix = new StringBuilder();
            boolean replaced = false;
            for (char c : word.toCharArray()) {
                if (!node.children.containsKey(c) || node.isEnd) break;
                prefix.append(c);
                node = node.children.get(c);
                if (node.isEnd) {
                    replaced = true;
                    break;
                }
            }
            if (sb.length() > 0) sb.append(" ");
            sb.append((node.isEnd) ? prefix.toString() : word);
        }
        return sb.toString();
    }
}
      

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

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

function replaceWords(dictionary, sentence) {
    const root = buildTrie(dictionary);
    function replace(word) {
        let node = root;
        let prefix = '';
        for (const char of word) {
            if (!node.children[char]) break;
            prefix += char;
            node = node.children[char];
            if (node.isEnd) return prefix;
        }
        return word;
    }
    return sentence.split(' ').map(replace).join(' ');
}
      

Problem Description

You are given a list of dictionary words, each considered as a "root". You are also given a sentence consisting of words separated by spaces.

The task is to replace all words in the sentence that have a root in the dictionary as a prefix with that root word. If a word in the sentence has multiple roots that can match as a prefix, you must replace it with the shortest such root.

Constraints:

• Each word in dictionary is a non-empty string of lowercase English letters.
• Each word in sentence is also a non-empty string of lowercase English letters.
• There is only one valid solution for each input.
• Do not reuse or overlap roots in a single word; each word is replaced at most once by the shortest matching root.

Thought Process

To solve this problem, let's first consider a naive or brute-force approach. For each word in the sentence, we could check every root in the dictionary to see if it is a prefix, and if so, replace the word with the shortest such root. This would involve a lot of repeated prefix checks, especially if the dictionary or sentence is large.

However, this brute-force method is inefficient. To optimize, we can leverage a data structure that supports fast prefix lookups: a Trie (prefix tree). By storing all roots in a Trie, we can efficiently determine the shortest matching root for any word by traversing the Trie character by character until we either find a matching root or determine that none exists.

This approach is both faster and more elegant, as it avoids redundant checks and leverages the hierarchical nature of prefixes.

Solution Approach

Here is a step-by-step explanation of the optimized solution using a Trie:

1. Build the Trie:
   • Create a root node for the Trie.
   • For each word (root) in the dictionary, insert it into the Trie character by character.
   • Mark the end of each root in the Trie (for example, with a special flag or symbol).
2. Process Each Word in the Sentence:
   • Split the sentence into individual words.
   • For each word, traverse the Trie from the root, following the path that matches the word's characters.
   • As you traverse, build up a prefix string.
   • If you reach a node in the Trie that marks the end of a root, replace the word with the current prefix (the root).
   • If you reach a character in the word that isn't in the Trie, or finish the traversal without finding a root, keep the original word.
3. Reconstruct the Sentence:
   • Join the processed words back together with spaces to form the final sentence.

Using a Trie ensures that finding the shortest root is efficient, because we stop at the first matching root during traversal.

Example Walkthrough

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

Step-by-step:

1. Insert "cat", "bat", and "rat" into the Trie.
2. Process each word:
   • the: No root matches. Keep "the".
   • cattle: "cat" is a prefix. Replace "cattle" with "cat".
   • was: No root matches. Keep "was".
   • rattled: "rat" is a prefix. Replace "rattled" with "rat".
   • by: No root matches. Keep "by".
   • the: No root matches. Keep "the".
   • battery: "bat" is a prefix. Replace "battery" with "bat".
3. Join the results: "the cat was rat by the bat"

At each step, the algorithm efficiently finds the shortest root using the Trie structure and replaces the word accordingly.

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(N * M * L), where N is the number of words in the sentence, M is the number of roots in the dictionary, and L is the average length of the words/roots. For each word, we check every root as a prefix.
• Space Complexity: O(M * L) to store the dictionary, plus O(N * L) for the sentence words.

• Time Complexity: O(D * L + S), where D is the number of roots, L is the average root length (for building the Trie), and S is the total number of characters in the sentence (since each word is traversed at most up to its length).
• Space Complexity: O(D * L) for the Trie, plus O(N * L) for sentence storage.

The Trie approach is significantly faster, especially when the dictionary is large or words are long, as it avoids redundant prefix checks.

Summary

In this problem, we efficiently replace words in a sentence with the shortest matching root from a dictionary by using a Trie (prefix tree). This data structure allows for quick prefix checks, making the solution much more efficient than brute-force approaches. The key insight is to stop the search as soon as the shortest matching root is found, ensuring both correctness and optimal performance.