Replace Words (Word Root Dictionary)

📋

Replace Words (Word Root Dictionary)

Edge cases:

</>

IDE

def replaceWords(dictionary: list[str], sentence: str) -> str:public String replaceWords(List<String> dictionary, String sentence)string replaceWords(vector<string> dictionary, string sentence)function replaceWords(dictionary, sentence)

def replaceWords(dictionary, sentence):
    # Write your solution here
    pass

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        // Write your solution here
        return null;
    }
}

#include <vector>
#include <string>
using namespace std;

string replaceWords(vector<string> dictionary, string sentence) {
    // Write your solution here
    return "";
}

function replaceWords(dictionary, sentence) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Words replaced by longest matching root prefix instead of shortestGreedy approach that continues searching for longer prefixes after finding a valid root✅ Stop trie traversal and return the first root found to ensure shortest prefix is used

Wrong: Words replaced even when no root prefix existsIncorrect substring matching instead of prefix matching✅ Check only prefix matches by verifying word starts with root or using trie traversal from start

Wrong: Program crashes or returns incorrect output on empty dictionaryNo handling for empty dictionary input✅ Add a condition to return original sentence if dictionary is empty

Wrong: Repeated words replaced inconsistently or skippedCaching or skipping repeated words incorrectly✅ Process each word independently without caching results

Wrong: Time limit exceeded on large inputsBrute force checking all roots for each word✅ Implement trie-based prefix search to reduce complexity to O(m*k)

✓

Test Cases

Try testing your solution with empty and minimal inputs to catch base case bugs.

Consider tricky cases where roots overlap or repeated words appear to catch logical errors.

Optimize your solution using a trie to handle large inputs efficiently.

t1_01basic

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

Expected"the cat was rat by the bat"

⏱ Performance - must finish in 2000ms

Words 'cattle', 'rattled', and 'battery' are replaced by their shortest root prefixes 'cat', 'rat', and 'bat' respectively.

💡 Consider how to efficiently find the shortest root prefix for each word.

💡 Use a trie to store roots and search prefixes quickly.

💡 For each word, traverse the trie character by character to find the shortest matching root.

Why it failed: Failed to replace words with their shortest root prefixes; likely missing prefix search or incorrect prefix length check. Fix by implementing trie prefix search and returning the shortest root found.

✓ Correctly replaced all words with their shortest root prefixes.

t1_02basic

Input{"dictionary":["a","aa","aaa"],"sentence":"a aa aaa aaaa"}

Expected"a a a a"

⏱ Performance - must finish in 2000ms

Each word is replaced by the shortest root prefix 'a' since it is a prefix of all words.

💡 Check how overlapping roots affect replacement.

💡 Ensure the shortest root prefix is chosen, not just any prefix.

💡 Stop searching once the shortest prefix is found in the trie.

Why it failed: Incorrectly replaced words with longer roots instead of the shortest prefix. Fix by stopping prefix search at the first found root in trie traversal.

✓ Shortest root prefixes correctly identified and used for replacement.

t2_01edge

Input{"dictionary":[],"sentence":"this sentence remains unchanged"}

Expected"this sentence remains unchanged"

⏱ Performance - must finish in 2000ms

Empty dictionary means no replacements; sentence remains unchanged.

💡 What happens if the dictionary is empty?

💡 Check if your code handles empty root list without errors.

💡 Return the original sentence unchanged if no roots exist.

Why it failed: Code crashes or modifies sentence when dictionary is empty. Fix by adding a check for empty dictionary and returning sentence as is.

✓ Handles empty dictionary correctly by returning original sentence.

t2_02edge

Input{"dictionary":["a"],"sentence":"b"}

Expected"b"

⏱ Performance - must finish in 2000ms

Word 'b' has no matching root prefix 'a', so it remains unchanged.

💡 Check words that have no matching root prefix.

💡 Ensure words without any prefix match are left unchanged.

💡 Return the original word if no root prefix found in trie.

Why it failed: Incorrectly replaces words without matching roots or crashes. Fix by returning original word if no prefix found.

✓ Leaves words without matching roots unchanged.

t2_03edge

Input{"dictionary":["a","ab","abc"],"sentence":"abc ab a"}

Expected"a a a"

⏱ Performance - must finish in 2000ms

Roots are prefixes of each other; shortest root 'a' replaces all words.

💡 Roots can be prefixes of other roots.

💡 Always choose the shortest root prefix for replacement.

💡 Stop searching once the shortest prefix is found in trie traversal.

Why it failed: Fails to choose shortest root prefix, replacing with longer roots. Fix by stopping prefix search at first root found.

✓ Correctly replaces with shortest root prefix among overlapping roots.

t2_04edge

Input{"dictionary":["a"],"sentence":"a"}

Expected"a"

⏱ Performance - must finish in 2000ms

Single element dictionary and sentence word equal; replacement is the word itself.

💡 Test minimal input with single root and single word.

💡 Ensure replacement works when word equals root.

💡 Return the root if it matches the word exactly.

Why it failed: Fails to replace word when it equals root; fix by allowing replacement when word starts with root and lengths are equal.

✓ Correctly replaces word equal to root.

t3_01corner

Input{"dictionary":["cat","bat","rat"],"sentence":"cattle cattle cattle"}

Expected"cat cat cat"

⏱ Performance - must finish in 2000ms

Repeated words each replaced independently by shortest root prefix 'cat'.

💡 Check if repeated words are replaced independently.

💡 Ensure no caching or skipping of repeated words.

💡 Process each word separately even if repeated.

Why it failed: Fails to replace repeated words consistently, possibly caching results incorrectly. Fix by processing each word independently.

✓ Repeated words replaced correctly and independently.

t3_02corner

Input{"dictionary":["a","aa","aaa"],"sentence":"aaaaa"}

Expected"a"

⏱ Performance - must finish in 2000ms

Tests greedy trap: must choose shortest prefix 'a', not longer roots.

💡 Beware of greedy approaches that pick longest prefix.

💡 Always return the shortest root prefix found.

💡 Stop trie traversal at first root node.

Why it failed: Greedy approach picks longest prefix 'aaa' instead of shortest 'a'. Fix by stopping search at first root found in trie.

✓ Shortest prefix chosen correctly, avoiding greedy trap.

t3_03corner

Input{"dictionary":["a","b"],"sentence":"ab ba"}

Expected"a b"

⏱ Performance - must finish in 2000ms

Tests confusion between prefix and substring: only prefixes count, not substrings.

💡 Check that only prefixes are considered, not substrings.

💡 Verify startswith condition for each root.

💡 Use trie traversal from start of word only.

Why it failed: Incorrectly replaces words based on substring match instead of prefix. Fix by checking only prefix matches via trie traversal.

✓ Correctly replaces only when root is prefix, not substring.

t4_01performance

Input{"dictionary":["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa","b","bb","bbb","bbbb","bbbbb","bbbbbb","bbbbbbb","bbbbbbbb","bbbbbbbbb","bbbbbbbbbb","c","cc","ccc","cccc","ccccc","cccccc","ccccccc","cccccccc","ccccccccc","cccccccccc","d","dd","ddd","dddd","ddddd","dddddd","ddddddd","dddddddd","ddddddddd","dddddddddd","e","ee","eee","eeee","eeeee","eeeeee","eeeeeee","eeeeeeee","eeeeeeeee","eeeeeeeeee","f","ff","fff","ffff","fffff","ffffff","fffffff","ffffffff","fffffffff","ffffffffff","g","gg","ggg","gggg","ggggg","gggggg","ggggggg","gggggggg","ggggggggg","gggggggggg","h","hh","hhh","hhhh","hhhhh","hhhhhh","hhhhhhh","hhhhhhhh","hhhhhhhhh","hhhhhhhhhh","i","ii","iii","iiii","iiiii","iiiiii","iiiiiii","iiiiiiii","iiiiiiiii","iiiiiiiiii","j","jj","jjj","jjjj","jjjjj","jjjjjj","jjjjjjj","jjjjjjjj","jjjjjjjjj","jjjjjjjjjj"],"sentence":"aaaaaaaaaajjjjjjjjjj aaaaaaaaajjjjjjjjjj aaaaaaaaaajjjjjjjjjj aaaaaaaaaajjjjjjjjjj aaaaaaaaaajjjjjjjjjj aaaaaaaaaajjjjjjjjjj aaaaaaaaaajjjjjjjjjj aaaaaaaaaajjjjjjjjjj aaaaaaaaaajjjjjjjjjj aaaaaaaaaajjjjjjjjjj"}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 dictionary roots, sentence with 10 words each length ~20; solution must run in O(m*k) time within 2 seconds.

💡 Brute force checking all roots per word is too slow.

💡 Use a trie to achieve O(m*k) time complexity.

💡 Build trie once and search prefixes efficiently for each word.

Why it failed: TLE due to brute force O(m*n*k) approach. Fix by implementing trie-based prefix search to reduce complexity to O(m*k).

✓ Efficient trie-based solution runs within time limits.

Practice

1. You are given an array of integers and multiple queries. Each query provides a number x and a limit m. For each query, you must find the maximum XOR of x with any array element less than or equal to m. Which approach guarantees an optimal solution for large inputs?

easy

A. Sort the array and queries, then use a bitwise trie to insert elements up to the query limit and find max XOR.

B. Use dynamic programming to store XOR results for all subarrays and answer queries in O(1).

C. Use a brute force nested loop checking all elements for each query.

D. Apply a greedy approach by always choosing the element with the highest value less than or equal to m.

Solution

1. Step 1: Understand problem constraints

   Brute force is too slow for large inputs; DP for subarrays doesn't apply since queries are arbitrary.

2. Step 2: Recognize the pattern

   Sorting nums and queries allows incremental trie insertion of eligible elements, enabling efficient max XOR queries.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + trie insertion matches known optimal approach [OK]

Hint: Sort queries and nums, then use bit trie [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Using DP for unrelated subproblems
• Greedy max element doesn't guarantee max XOR

2. Examine the following buggy search method for the WordDictionary implemented with a trie. Which line contains the subtle bug that causes incorrect search results for patterns with '.' wildcard?

def search(self, word: str) -> bool:
    stack = [(0, self.root)]
    while stack:
        index, node = stack.pop()
        if index == len(word):
            if node.is_end:
                return True
            continue
        ch = word[index]
        if ch == '.':
            for child in node.children:
                stack.append((index + 1, child))
        else:
            if ch in node.children:
                stack.append((index + 1, node.children[ch]))
    return False

medium

A. Line with 'stack = [(0, self.root)]'

B. Line with 'for child in node.children:'

C. Line with 'if node.is_end:'

D. Line with 'if ch in node.children:'

Solution

1. Step 1: Identify how children are iterated for '.' wildcard

   The code uses 'for child in node.children:', which iterates over keys (characters), not child nodes.

2. Step 2: Understand impact of iterating keys instead of nodes

   Appending keys instead of TrieNode objects causes incorrect stack entries and search failure.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Must iterate over node.children.values() to get child nodes [OK]

Hint: Iterate node.children.values(), not keys [OK]

Common Mistakes:

• Iterating keys instead of child nodes
• Forgetting to mark is_end
• Misplacing base case check

3. What is the time complexity of the optimal trie + BFS approach for finding the longest word in a dictionary with n words, each of average length m?

medium

A. O(n * m + n * 26) because building trie takes O(n*m) and BFS visits each node once

B. O(n * m * 26) since BFS explores all children for each character

C. O(n * m^2) due to checking all prefixes for each word

D. O(n * m log n) due to sorting children at each node during BFS

Solution

1. Step 1: Analyze trie construction

   Inserting n words of length m takes O(n * m) time as each character is processed once.

2. Step 2: Analyze BFS traversal

   BFS visits each node once; each node has up to 26 children, so total BFS cost is O(n * 26) which is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie build + BFS traversal sum to O(n*m + n*26) [OK]

Hint: Trie build O(n*m), BFS O(n*26) combined [OK]

Common Mistakes:

• Confusing BFS cost as O(n*m*26)
• Forgetting BFS visits each node once
• Assuming sorting children adds log factor per node

4. Examine the following buggy snippet from the Trie + DFS solution. Which line contains the subtle bug that can cause incorrect results or infinite loops?

def dfs(r, c, node):
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return
    char = board[r][c]
    if char == '#' or char not in node.children:
        return
    node = node.children[char]
    if node.word:
        result.append(node.word)
        node.word = None
    # BUG: Missing marking visited cell
    dfs(r+1, c, node)
    dfs(r-1, c, node)
    dfs(r, c+1, node)
    dfs(r, c-1, node)
    # BUG: Missing restoring cell after DFS

medium

A. Line checking if char == '#' or char not in node.children

B. Lines calling dfs recursively without marking visited cells

C. Line appending node.word to result and setting node.word = None

D. Line updating node = node.children[char]

Solution

1. Step 1: Identify missing visited cell marking

   The code does not mark the current cell as visited before recursive calls, allowing revisits and potential infinite loops.

2. Step 2: Identify missing restoring cell state

   Without restoring the cell after DFS, subsequent searches see corrupted board state, causing incorrect results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing visited marking causes infinite loops or incorrect word detection [OK]

Hint: Always mark and restore visited cells in DFS [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Not restoring board state after DFS
• Appending duplicates without clearing node.word

5. Suppose the problem is modified so that each letter cell on the board can be reused multiple times within the same word (i.e., no visited marking needed). Which modification to the Trie + DFS algorithm correctly handles this variant without causing infinite loops or incorrect results?

hard

A. Remove visited marking and add a depth limit equal to the maximum word length to prevent infinite recursion.

B. Use BFS instead of DFS to avoid revisiting cells infinitely.

C. Keep visited marking but reset it after each DFS call to allow reuse.

D. Remove visited marking and keep DFS as is; no other changes needed.

Solution

1. Step 1: Understand reuse allows cycles

   Without visited marking, DFS can revisit the same cell infinitely, causing infinite recursion.

2. Step 2: Add depth limit to DFS

   Limiting recursion depth to the maximum word length prevents infinite loops while allowing reuse of cells.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Depth limit bounds recursion, enabling correct search with reuse [OK]

Hint: Depth limit prevents infinite recursion when reuse allowed [OK]

Common Mistakes:

• Removing visited marking without depth limit causes infinite loops
• Keeping visited marking contradicts reuse
• Switching to BFS doesn't solve infinite recursion