Replace Words (Word Root Dictionary)

▶

Steps

setup

Initialize Trie Root

Create the root node of the trie, which is empty and has no children yet.

💡 The root node is the starting point for all insertions and searches in the trie.

Line:

class Trie:
    def __init__(self):
        self.root = TrieNode()

💡 The trie starts empty with a single root node.

insert

Insert root 'cat' - Insert 'c'

Insert the first character 'c' of the root word 'cat' into the trie as a child of the root node.

💡 Inserting characters one by one builds the trie structure representing dictionary roots.

Line:

for char in word:
    if char not in node.children:
        node.children[char] = TrieNode()
    node = node.children[char]

💡 New branches are created in the trie when characters are not already present.

insert

Insert root 'cat' - Insert 'a'

Insert the next character 'a' of 'cat' as a child of node 'c'.

💡 Each character extends the path in the trie representing the root word.

Line:

if char not in node.children:
    node.children[char] = TrieNode()
node = node.children[char]

💡 Trie nodes are linked to form the full root word path.

insert

Insert root 'cat' - Insert 't' and mark end

Insert the last character 't' of 'cat' and mark this node as end of a root word.

💡 Marking end_of_word identifies valid root words in the trie.

Line:

node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True

💡 End markers allow prefix searches to stop early when a root is found.

insert

Insert root 'bat' - Insert 'b'

Start inserting the next root 'bat' by adding 'b' as a child of root node.

💡 New root words create new branches from the root node.

Line:

for root in dictionary:
    trie.insert(root)

💡 Trie branches represent different root prefixes.

insert

Insert root 'bat' - Insert 'a'

Insert 'a' as a child of 'b' node for root 'bat'.

💡 Continuing to build the path for the root word.

Line:

if char not in node.children:
    node.children[char] = TrieNode()
node = node.children[char]

💡 Each character extends the root word path in the trie.

insert

Insert root 'bat' - Insert 't' and mark end

Insert 't' as child of 'a' and mark this node as end of root 'bat'.

💡 Marking end_of_word signals a complete root word in the trie.

Line:

node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True

💡 End markers allow prefix search to stop early when a root is found.

insert

Insert root 'rat' - Insert 'r'

Insert 'r' as a new child of root node for root 'rat'.

💡 New root words create new branches from the root node.

Line:

for root in dictionary:
    trie.insert(root)

💡 Trie branches represent different root prefixes.

insert

Insert root 'rat' - Insert 'a'

Insert 'a' as child of 'r' node for root 'rat'.

💡 Continuing to build the path for the root word.

Line:

if char not in node.children:
    node.children[char] = TrieNode()
node = node.children[char]

💡 Each character extends the root word path in the trie.

insert

Insert root 'rat' - Insert 't' and mark end

Insert 't' as child of 'a' and mark this node as end of root 'rat'.

💡 Marking end_of_word signals a complete root word in the trie.

Line:

node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True

💡 End markers allow prefix search to stop early when a root is found.

setup

Split sentence into words

Split the sentence into individual words to process each for replacement.

💡 Processing each word separately allows prefix search in the trie.

Line:

words = sentence.split()

💡 The sentence is now ready for prefix replacement word by word.

search

Search prefix for word 'the' - Check 't'

Start searching for shortest root prefix of 'the' by checking if 't' is a child of root.

💡 Prefix search tries to find a root matching the start of the word.

Line:

for char in word:
    if char not in node.children:
        return None

💡 If first character not in trie, no root prefix exists for this word.

search

Search prefix for word 'cattle' - Check 'c'

Start searching for shortest root prefix of 'cattle' by checking 'c' child of root.

💡 We try to find a root prefix starting with 'c'.

Line:

node = node.children[char]
prefix += char
if node.is_end:
    return prefix

💡 Traversal continues as character matches a trie child.

search

Search prefix for word 'cattle' - Check 'a'

Continue searching by checking 'a' child of node 'c'.

💡 We continue matching characters to find a root prefix.

Line:

node = node.children[char]
prefix += char
if node.is_end:
    return prefix

💡 Traversal continues as characters match trie nodes.

search

Search prefix for word 'cattle' - Check 't' and find end

Check 't' child of 'a' node; node is end of root 'cat', so stop and return prefix 'cat'.

💡 Finding an end_of_word node means shortest root prefix found.

Line:

node = node.children[char]
prefix += char
if node.is_end:
    return prefix

💡 Shortest root prefix replaces the word.

search

Search prefix for word 'rattled' - Check 'r'

Start searching for shortest root prefix of 'rattled' by checking 'r' child of root.

💡 We try to find a root prefix starting with 'r'.

Line:

for char in word:
    if char not in node.children:
        return None

💡 Traversal continues as character matches a trie child.

search

Search prefix for word 'rattled' - Check 'a'

Continue searching by checking 'a' child of node 'r'.

💡 We continue matching characters to find a root prefix.

Line:

node = node.children[char]
prefix += char
if node.is_end:
    return prefix

💡 Traversal continues as characters match trie nodes.

search

Search prefix for word 'rattled' - Check 't' and find end

Check 't' child of 'a' node; node is end of root 'rat', so stop and return prefix 'rat'.

💡 Finding an end_of_word node means shortest root prefix found.

Line:

node = node.children[char]
prefix += char
if node.is_end:
    return prefix

💡 Shortest root prefix replaces the word.

search

Search prefix for word 'battery' - Check 'b'

Start searching for shortest root prefix of 'battery' by checking 'b' child of root.

💡 We try to find a root prefix starting with 'b'.

Line:

for char in word:
    if char not in node.children:
        return None

💡 Traversal continues as character matches a trie child.

search

Search prefix for word 'battery' - Check 'a' and 't' and find end

Traverse 'a' then 't' nodes; node 't' is end of root 'bat', so return prefix 'bat'.

💡 Finding an end_of_word node means shortest root prefix found.

Line:

node = node.children[char]
prefix += char
if node.is_end:
    return prefix

💡 Shortest root prefix replaces the word.

reconstruct

Form final replaced sentence

Join all replaced words into the final sentence: 'the cat was rat by the bat'.

💡 Combining replaced words produces the final output.

Line:

return ' '.join(result)

💡 The algorithm successfully replaced words by their shortest root prefixes.

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

class Trie:
    def __init__(self):
        self.root = TrieNode()  # STEP 1

    def insert(self, word):
        node = self.root
        for char in word:  # STEP 2-10
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search_shortest_prefix(self, word):
        node = self.root
        prefix = ''
        for char in word:  # STEP 12-20
            if char not in node.children:
                return None
            node = node.children[char]
            prefix += char
            if node.is_end:
                return prefix
        return None

def replaceWords(dictionary, sentence):
    trie = Trie()
    for root in dictionary:  # STEP 2-10
        trie.insert(root)
    words = sentence.split()  # STEP 11
    result = []
    for word in words:  # STEP 12-20
        prefix = trie.search_shortest_prefix(word)
        result.append(prefix if prefix else word)
    return ' '.join(result)  # STEP 21

if __name__ == '__main__':
    dict_roots = ["cat", "bat", "rat"]
    sentence = "the cattle was rattled by the battery"
    print(replaceWords(dict_roots, sentence))

📊

Replace Words (Word Root Dictionary) - Watch the Algorithm Execute, Step by Step

Watching the trie construction and prefix search step-by-step reveals how the algorithm efficiently replaces words by their roots without scanning the entire dictionary for each word.

insert

insert

cat

c

insert

cat

ca

insert

cat

at*

insert

bat

b

insert

bat

ba

insert

bat

at*

insert

rat

r

insert

rat

ra

insert

rat

at*

search

search

the

Search: false

search

cattle

c

search

cattle

ca

search

cattle

at*

Search: true

search

rattled

r

search

rattled

ra

search

rattled

at*

Search: true

search

battery

b

search

battery

at*

Search: true

reconstruct

Key Takeaways

✓ Building a trie from dictionary roots allows efficient prefix searches for replacement.

This is hard to see from code alone because the trie structure and its incremental growth are abstract without visualization.

✓ The search stops as soon as an end_of_word node is found, ensuring the shortest root prefix is used.

Understanding early stopping in the trie traversal clarifies why the shortest prefix is chosen.

✓ Words without any matching root prefix remain unchanged, preserving sentence meaning.

Seeing the failed search path visually helps understand why some words are not replaced.

Practice

1. You need to design a data structure that supports inserting key-value pairs and efficiently returning the sum of all values of keys that start with a given prefix. Which approach guarantees the most optimal time complexity for both insert and sum operations?

easy

A. Use a hash map to store all keys and values, and scan all keys on each sum query to accumulate matching prefixes.

B. Use a dynamic programming approach to precompute sums for all possible prefixes and update them on each insert.

C. Use a balanced binary search tree keyed by strings, and perform range queries for prefix sums.

D. Use a trie where each node stores the cumulative sum of all keys passing through it, updating sums on insert and traversing prefix nodes on sum queries.

Solution

1. Step 1: Understand the problem requirements

   The data structure must support fast insertions and prefix sum queries.

2. Step 2: Evaluate approaches

   Hash map with scanning is O(n*k) per sum, which is inefficient. Balanced BST range queries are complex and slower. DP precomputation is infeasible for dynamic inserts. Trie with prefix sums allows O(k) insert and sum operations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Trie prefix sums enable O(k) operations [OK]

Hint: Trie with prefix sums supports O(k) insert and sum [OK]

Common Mistakes:

• Thinking brute force scanning is efficient enough
• Using BSTs for prefix sums
• Trying DP precomputation for dynamic keys

2. Given the following code snippet for MapSum, after inserting keys "apple" with value 3 and "app" with value 2, what is the value of node.sum at the trie node corresponding to 'p' (the second character) after the second insert?

easy

A. 3

B. 5

C. 2

D. 0

Solution

1. Step 1: Trace insert of "apple" with value 3

   Delta = 3 - 0 = 3. Root.sum += 3 -> 3. For each character 'a','p','p','l','e', node.sum += 3. After first insert, node at second 'p' has sum 3.

2. Step 2: Trace insert of "app" with value 2

   Delta = 2 - 0 = 2. Root.sum += 2 -> 5. For 'a','p','p', node.sum += 2. Node at second 'p' sum was 3, now 3 + 2 = 5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum at second 'p' after both inserts is 5 [OK]

Hint: Sum accumulates delta on each insert per prefix node [OK]

Common Mistakes:

• Forgetting to add delta on second insert
• Confusing first and second 'p' nodes
• Using old value instead of delta

3. Consider the following buggy Trie insert method. Which line contains the subtle bug that causes search to fail for inserted words?

medium

A. Line where node = self.root is assigned

B. Line where node = node.children[ch] is assigned inside the loop

C. Line where isEnd flag should be set but is missing

D. Line where the if condition checks if ch not in node.children

Solution

1. Step 1: Identify missing isEnd flag set

   After inserting all characters, isEnd must be set true to mark word end. This line is missing.

2. Step 2: Understand impact on search

   Without isEnd=true, search returns false even if path exists, because node.isEnd remains false.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing isEnd assignment causes search failure for inserted words [OK]

Hint: isEnd must be set after inserting entire word [OK]

Common Mistakes:

• Forgetting to mark isEnd after insertion

4. The following code attempts to find the maximum XOR of two numbers using a bitwise trie. Identify the bug that causes incorrect results or runtime errors for edge cases.

medium

A. Not handling the case when nums has only one element, causing incorrect max_xor

B. Incorrect bit shifting in line extracting bit from num

C. Not updating max_xor after processing each number

D. Using dictionary for children instead of fixed-size array

Solution

1. Step 1: Consider edge case of single element array

   If nums has only one element, the maximum XOR should be 0, but code does not explicitly handle this and may return incorrect or crash.

2. Step 2: Check other lines

   Bit shifting and max_xor update lines are correct; using dictionary is valid though less efficient.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single element input requires special handling to avoid incorrect result [OK]

Hint: Single element arrays need special XOR handling [OK]

Common Mistakes:

• Assuming input size >= 2 without checks

5. Suppose the autocomplete system must now support returning the top 5 suggestions instead of 3, and the products list can be updated dynamically with insertions. Which modification to the trie-based approach is most appropriate to maintain efficient queries?

hard

A. Increase the suggestions list size to 5 at each node and rebuild the entire trie after each insertion.

B. Store all products at each node and filter top 5 suggestions during query time.

C. Switch to brute force filtering and sorting after each insertion to avoid trie complexity.

D. Use a balanced search tree or heap at each node to maintain top 5 suggestions dynamically during insertions.

Solution

1. Step 1: Understand dynamic updates and top-K requirement

   Supporting dynamic insertions and top 5 suggestions requires efficient updates and queries without rebuilding the entire trie.

2. Step 2: Evaluate data structures for suggestions

   Using a balanced tree or min-heap at each node allows maintaining top 5 suggestions dynamically as products are inserted, avoiding costly rebuilds.

3. Step 3: Reject naive approaches

   Rebuilding trie after each insertion is inefficient. Brute force filtering is too slow. Storing all products at each node wastes space and slows queries.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Balanced structures enable efficient dynamic top-K maintenance [OK]

Hint: Use balanced structures at nodes for dynamic top-K updates [OK]

Common Mistakes:

• Rebuilding trie on every insertion
• Ignoring dynamic update costs
• Storing all products at nodes