Leetcode 648. Replace Words

Problem

You are building a text compression system that simplifies words by replacing them with their root forms. Given a list of root words and a sentence, transform the sentence by replacing each word with the shortest root that appears as a prefix of that word. If no root matches, keep the original word.

For example, if "cat" is a root and "cattle" appears in the sentence, replace "cattle" with "cat". When multiple roots could match a word, always use the shortest one.

Return the transformed sentence as a string with words separated by single spaces.

Requirements

1. Parse the input sentence into individual words
2. For each word, find all roots that are prefixes of that word
3. Replace the word with the shortest matching root (or keep the original if no match)
4. Reconstruct and return the transformed sentence

Constraints

• 1 ≤ roots.length ≤ 1000
• 1 ≤ roots[i].length ≤ 100
• All roots consist of lowercase English letters
• 1 ≤ sentence.length ≤ 10^6
• The sentence consists of lowercase English letters and spaces
• There are no leading or trailing spaces
• All words in the sentence are separated by a single space

Examples

Example 1:

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

Output: "the cat was rat by the bat"

Explanation:

• "cattle" starts with "cat" → replace with "cat"
• "rattled" starts with "rat" → replace with "rat"
• "battery" starts with "bat" → replace with "bat"
• Other words have no matching roots `

Example 2:

` Input: roots = ["a", "b", "c"] sentence = "aadsfasf absbs bbab cadsfafs"

Output: "a a b c"

Explanation:

• "aadsfasf" starts with "a" → replace with "a"
• "absbs" starts with "a" → replace with "a"
• "bbab" starts with "b" → replace with "b"
• "cadsfafs" starts with "c" → replace with "c" `

Example 3:

` Input: roots = ["catt", "cat", "bat", "rat"] sentence = "the cattle was rattled by the battery"

Output: "the cat was rat by the bat"

Explanation: When multiple roots match (both "cat" and "catt" match "cattle"), use the shortest one ("cat"). `

Hint 1: Brute Force Approach For each word in the sentence, check every root in the list to see if it's a prefix of the word. Keep track of the shortest matching root and use it for replacement. This approach works but may be slow with many roots or long words.

Hint 2: Optimizing Prefix Search A Trie (prefix tree) data structure is ideal for this problem. Build a trie from all roots, then for each word in the sentence, traverse the trie character by character. The first complete root you encounter is automatically the shortest matching root.

Hint 3: Early Termination When searching for a matching root in the trie, you can stop as soon as you find a complete root word. Since you're checking prefixes from shortest to longest, the first match is guaranteed to be the shortest.

Full Solution `` Approach:

1. Build a Trie: Create a trie data structure and insert all root words. Each node marks whether it represents the end of a root word.
2. Process Each Word: Split the sentence and process each word independently.
3. Find Shortest Root: For each word, traverse the trie character by character. As soon as we reach a node marked as a root, we've found the shortest matching root (since we're checking prefixes in order from shortest to longest).
4. Reconstruct Sentence: Build the result by joining all replaced/original words with spaces.

Time Complexity: O(N + M) where N is the total length of all roots and M is the length of the sentence. Building the trie takes O(N), and processing the sentence takes O(M) since each character is examined at most once.

Space Complexity: O(N) for the trie structure storing all roots, plus O(M) for the output string.

Alternative Simpler Approach:

If the constraints allow (smaller inputs), you can use a simpler hash set approach:

` def replaceWords(roots, sentence): root_set = set(roots) words = sentence.split() result = []

for word in words:
    # Try all possible prefixes from shortest to longest
    replacement = word
    for i in range(1, len(word) + 1):
        prefix = word[:i]
        if prefix in root_set:
            replacement = prefix
            break
    result.append(replacement)

return ' '.join(result)

`

This approach is simpler but has O(M × L) time complexity where L is the average word length, as we check each prefix against the set.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_root = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        """Insert a root word into the trie"""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_root = True
    
    def find_shortest_root(self, word):
        """Find the shortest root that is a prefix of the given word"""
        node = self.root
        prefix = []
        
        for char in word:
            if char not in node.children:
                # No matching root found
                return word
            
            prefix.append(char)
            node = node.children[char]
            
            # Found a root - return immediately (it's the shortest)
            if node.is_root:
                return ''.join(prefix)
        
        # No root found, return original word
        return word

def replaceWords(roots, sentence):
    # Build trie from all roots
    trie = Trie()
    for root in roots:
        trie.insert(root)
    
    # Process each word in the sentence
    words = sentence.split()
    result = []
    
    for word in words:
        # Find shortest matching root or keep original word
        replacement = trie.find_shortest_root(word)
        result.append(replacement)
    
    return ' '.join(result)