LeetCode 648: Replace Words Solution in Python – A Step-by-Step Guide

What Is LeetCode 648: Replace Words?

In LeetCode 648: Replace Words, you’re given a list dictionary of root words and a string sentence. Your task is to replace each word in the sentence with the shortest root from dictionary that is a prefix of the word, if such a root exists; otherwise, keep the original word. Return the modified sentence as a string. For example, with dictionary = ["cat", "bat", "rat"] and sentence = "the cattle was rattled by the battery", you’d replace "cattle" with "cat", "rattled" with "rat", and "battery" with "bat", yielding "the cat was rat by the bat". This problem tests your ability to perform prefix matching efficiently across multiple words.

Problem Statement

• Input:
• dictionary: List of strings (root words).
• sentence: String of space-separated words.
• Output: A string—sentence with words replaced by shortest matching roots.
• Rules:
• Replace word with shortest root that’s a prefix, if any.
• Keep original word if no root matches.
• Return modified sentence with spaces.

Constraints

• 1 ≤ dictionary.length ≤ 1000.
• 1 ≤ dictionary[i].length ≤ 100.
• 1 ≤ sentence.length ≤ 10⁶.
• dictionary[i] and sentence words are lowercase letters.
• Sentence contains at least one word, separated by spaces.

Examples

• Input: dictionary = ["cat", "bat", "rat"], sentence = "the cattle was rattled by the battery"
• Output: "the cat was rat by the bat"
• Input: dictionary = ["a", "b", "c"], sentence = "aadsfasf absbs bbab cadsfafs"
• Output: "a a b c"
• Input: dictionary = ["a"], sentence = "b"
• Output: "b" (No prefix match)

These examples set the words—let’s solve it!

Understanding the Problem: Replacing with Roots

To solve LeetCode 648: Replace Words in Python, we need to process a sentence, splitting it into words, and for each word, find the shortest prefix that matches a root from the dictionary, replacing it if found. A brute-force approach—checking every root against every word—would be O(n * m * k), where n is dictionary size, m is number of words, and k is average word length, inefficient for n ≤ 1000 and sentence length ≤ 10⁶. Since we’re looking for prefixes, we can optimize with a trie or hash set. We’ll use:

• Best Solution (Trie-Based Prefix Replacement): O(N + M) time, O(N) space—fast and scalable (N = total chars in dictionary, M = total chars in sentence).
• Alternative Solution (Hash Set with String Checking): O(n m k) time, O(n) space—simpler but slower.

Let’s start with the trie solution, breaking it down for beginners.

Best Solution: Trie-Based Prefix Replacement

Why This Is the Best Solution

The trie-based prefix replacement is the top choice for LeetCode 648 because it’s efficient—O(N + M) time with O(N) space—and uses a trie (prefix tree) to quickly find the shortest matching root for each word in the sentence, avoiding repeated prefix checks. It fits constraints (n ≤ 1000, sentence length ≤ 10⁶) perfectly and scales well for large inputs. It’s like a prefix dictionary that finds matches in a snap!

How It Works

Think of this as a prefix finder:

• Step 1: Build Trie:
• Insert each root from dictionary into a trie, marking end nodes with the root word.
• Step 2: Process Sentence:
• Split sentence into words.
• For each word:
• Traverse trie char by char.
• If an end node is hit, use that root; otherwise, keep original word.
• Step 3: Rebuild Sentence:
• Join replaced words with spaces.
• Step 4: Return Result:
• Return modified sentence.

It’s like a root scanner—trie and replace!

Step-by-Step Example

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

• Step 1: Build Trie:
• Root → {c: {a: {t: {end: "cat"}}}, b: {a: {t: {end: "bat"}}}, r: {a: {t: {end: "rat"}}}}.
• Step 2: Process Words:
• "the": No match, keep "the".
• "cattle": Traverse c-a-t (end: "cat"), replace with "cat".
• "was": No match, keep "was".
• "rattled": Traverse r-a-t (end: "rat"), replace with "rat".
• "by": No match, keep "by".
• "battery": Traverse b-a-t (end: "bat"), replace with "bat".
• Step 3: Join: "the cat was rat by the bat".
• Output: "the cat was rat by the bat".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None  # Root word if end of root

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        # Step 1: Build trie from dictionary
        root = TrieNode()
        for word in dictionary:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.word = word  # Mark end with root word

        # Step 2: Process sentence
        words = sentence.split()
        for i in range(len(words)):
            node = root
            for j, char in enumerate(words[i]):
                if char not in node.children:
                    break  # No prefix match, keep word
                node = node.children[char]
                if node.word:
                    words[i] = node.word  # Replace with shortest root
                    break

        # Step 3: Rebuild sentence
        return " ".join(words)

• Lines 1-5: TrieNode: Children map, word marker.
• Lines 9-17: Build trie:
• Insert each root, mark end with word.
• Lines 20-29: Process:
• Split sentence, traverse trie per word, replace with root if found.
• Line 32: Join words with spaces.
• Time Complexity:
• Build: O(N) (N = total chars in dictionary).
• Process: O(M) (M = total chars in sentence).
• Space Complexity: O(N)—trie size.

This is like a prefix replacer—trie and swap!

Alternative Solution: Hash Set with String Checking

Why an Alternative Approach?

The hash set with string checking uses a set of roots—O(n * m * k) time, O(n) space (n = dictionary size, m = word count, k = avg word length). It’s simpler, checking each root against each word, but slower due to repeated prefix comparisons. It’s like a basic root checker with a list!

How It Works

Picture this as a root matcher:

• Step 1: Build set from dictionary.
• Step 2: Process sentence:
• Split into words.
• For each word, check all roots for prefix match, take shortest.
• Step 3: Join modified words.
• Step 4: Return result.

It’s like a root scanner—check and replace!

Step-by-Step Example

Example: Same as above

• Step 1: Set = {"cat", "bat", "rat"}.
• Step 2: Process:
• "the": No match, keep "the".
• "cattle": "cat" matches (shortest), replace with "cat".
• "was": No match, keep "was".
• "rattled": "rat" matches, replace with "rat".
• "by": No match, keep "by".
• "battery": "bat" matches, replace with "bat".
• Step 3: Join: "the cat was rat by the bat".
• Output: "the cat was rat by the bat".

Code for Hash Set Approach

Copy codeclass Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        # Step 1: Build set from dictionary
        root_set = set(dictionary)

        # Step 2: Process sentence
        words = sentence.split()
        for i in range(len(words)):
            word = words[i]
            for j in range(1, len(word) + 1):
                prefix = word[:j]
                if prefix in root_set:
                    words[i] = prefix  # Replace with shortest root
                    break

        # Step 3: Rebuild sentence
        return " ".join(words)

• Line 4: Build set of roots.
• Lines 7-13: Process:
• Check prefixes of each word, replace with shortest root.
• Line 16: Join words.
• Time Complexity: O(n m k)—n roots, m words, k avg length.
• Space Complexity: O(n)—set size.

It’s a root checker—simple but slower!

Comparing the Two Solutions

• Trie-Based (Best):
• Pros: O(N + M) time, O(N) space, fast prefix matching.
• Cons: Trie complexity.
• Hash Set (Alternative):
• Pros: O(n m k) time, O(n) space, straightforward.
• Cons: Slower due to repeated checks.

Trie wins for efficiency.

Additional Examples and Edge Cases

• Input: dictionary = ["a"], sentence = "b"
• Output: "b".
• Input: dictionary = ["ab", "a"], sentence = "abc"
• Output: "a".

Both handle these well.

Complexity Breakdown

• Trie: Time O(N + M), Space O(N).
• Hash Set: Time O(n m k), Space O(n).

Trie is optimal.

Key Takeaways

• Trie: Prefix speed—smart!
• Hash Set: Simple checks—clear!
• Replacement: Roots are fun.
• Python Tip: Tries rock—see Python Basics.

Final Thoughts: Replace Those Words

LeetCode 648: Replace Words in Python is a neat string challenge. Trie-based replacement offers speed and scalability, while hash set provides a clear baseline. Want more? Try LeetCode 208: Implement Trie or LeetCode 676: Implement Magic Dictionary. Ready to refine? Head to Solve LeetCode 648 on LeetCode and replace those words today!