Solution Explanation for LeetCode 648: Replace Words

This problem involves replacing words in a sentence with their shortest root word from a given dictionary. The optimal approach uses a Trie data structure for efficient root lookup.

Approach:

1. Trie Construction: We build a Trie from the words in the dictionary. Each node in the Trie represents a character, and each path from the root to a leaf node represents a root word. We store the index of the root word in the leaf node.

2. Sentence Processing: We iterate through the words in the sentence. For each word, we traverse the Trie. If we find a root word prefix in the Trie (indicated by a non-null ref value in the Trie node), we replace the word with that root word. If no root prefix is found, we keep the original word.

3. Result Construction: We concatenate the processed words with spaces to form the final replaced sentence.

Time Complexity Analysis:

• Trie Construction: Inserting each word into the Trie takes O(L) time, where L is the average length of a word in the dictionary. With N words in the dictionary, the total time complexity for Trie construction is O(N*L).

• Sentence Processing: For each word in the sentence (M words), we traverse the Trie. In the worst case, we may traverse the entire Trie for each word, taking O(L) time. Therefore, the total time for sentence processing is O(M*L).

• Overall Time Complexity: The dominant factor is the sentence processing, so the overall time complexity is O(ML + NL), which simplifies to O(M*L) assuming M and N are of similar order of magnitude. This is significantly faster than a naive approach that involves string comparisons for every word in the dictionary.

Space Complexity Analysis:

• The Trie's space complexity is proportional to the total number of characters in the dictionary words, which is O(N*L).
• The space used for the sentence processing is proportional to the length of the sentence, which is O(M).
• The overall space complexity is O(N*L + M).

Code Explanation (Python3):

class Trie:
    def __init__(self):
        self.children = [None] * 26  # Array for children (a-z)
        self.ref = -1               # Index of root word if found
 
    def insert(self, word, index):
        node = self
        for char in word:
            idx = ord(char) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.ref = index             # Mark leaf node with root index
 
    def search(self, word):
        node = self
        for char in word:
            idx = ord(char) - ord('a')
            if node.children[idx] is None:
                return -1       # Not found
            node = node.children[idx]
            if node.ref != -1:    # Root found
                return node.ref
        return -1                   # Not found
 
 
class Solution:
    def replaceWords(self, dictionary, sentence):
        trie = Trie()
        for i, word in enumerate(dictionary):
            trie.insert(word, i)
 
        result = []
        for word in sentence.split():
            index = trie.search(word)
            result.append(dictionary[index] if index != -1 else word)
        return " ".join(result)
 

The other language implementations (Java, C++, Go, TypeScript) follow a similar structure, using a Trie for efficient root word lookup and then replacing words in the sentence accordingly. The core logic remains the same across different languages.