Replace Words (Word Root Dictionary)

🎯

Replace Words (Word Root Dictionary)

mediumTRIEAmazonGoogleFacebook

Imagine you have a dictionary of root words and want to replace words in a sentence with their shortest root form to simplify text processing.

💡 This problem involves efficiently finding the shortest prefix from a dictionary that matches each word in a sentence. Beginners often struggle because naive methods check every root against every word, leading to slow solutions. Understanding tries helps optimize prefix searches.

📋

Problem Statement

Given a dictionary consisting of many root words and a sentence, replace all the words in the sentence with the shortest root word from the dictionary that is a prefix of the word. If a word has no root prefix in the dictionary, keep it unchanged. Return the modified sentence.

1 ≤ number of roots in dictionary ≤ 10^51 ≤ length of each root ≤ 1001 ≤ length of sentence ≤ 10^6 charactersAll words consist of lowercase English letters only

💡

Example

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

Output"the cat was rat by the bat"

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

• Empty dictionary → sentence remains unchanged
• Sentence with words that have no matching root → those words remain unchanged
• Roots that are prefixes of other roots → shortest root should be chosen
• Sentence with repeated words → each occurrence replaced independently

⚠️

Common Mistakes

Not stopping at shortest prefix in trie search

Longer prefixes replace shorter ones incorrectly

✅ Return immediately when is_end is true during trie traversal

Checking all roots for every word without early break

Unnecessary computations causing timeouts

✅ Break loop once shortest prefix found

Not handling words with no matching root

Replacing with empty string or error

✅ Return original word if no prefix found

Incorrect splitting of sentence into words

Wrong output or runtime errors

✅ Use reliable split methods or manual parsing

Using mutable default arguments in Python functions

Unexpected shared state bugs

✅ Avoid mutable defaults or initialize inside function

🧠

Brute Force (Check Each Word Against All Roots)

💡 This approach exists to build intuition by directly implementing the problem statement without optimization. It helps beginners understand the problem deeply before optimizing.

Intuition

For each word in the sentence, check every root in the dictionary to see if it is a prefix. Replace the word with the shortest matching root if any.

Algorithm

1. Split the sentence into words.
2. For each word, iterate over all roots in the dictionary.
3. Check if the root is a prefix of the word.
4. Replace the word with the shortest matching root if found; otherwise, keep the word.
5. Join all words back into a sentence.

💡 The nested loops make it hard to see efficiency issues at first, but it clearly shows the problem's core.

</>

Code

def replaceWords(dictionary, sentence):
    words = sentence.split()
    result = []
    for word in words:
        replacement = word
        for root in dictionary:
            if word.startswith(root) and len(root) < len(replacement):
                replacement = root
        result.append(replacement)
    return ' '.join(result)

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

Line Notes

words = sentence.split()Split sentence into individual words for processing

for word in words:Process each word independently

replacement = wordInitialize replacement as the original word

for root in dictionary:Check every root to find prefix matches

if word.startswith(root) and len(root) < len(replacement):Update replacement if root is a shorter prefix

result.append(replacement)Add the chosen replacement to the result list

return ' '.join(result)Reconstruct the sentence from replaced words

import java.util.*;
public class ReplaceWords {
    public static String replaceWords(List<String> dictionary, String sentence) {
        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String word : words) {
            String replacement = word;
            for (String root : dictionary) {
                if (word.startsWith(root) && root.length() < replacement.length()) {
                    replacement = root;
                }
            }
            sb.append(replacement).append(" ");
        }
        return sb.toString().trim();
    }

    public static void main(String[] args) {
        List<String> dict = Arrays.asList("cat", "bat", "rat");
        String sentence = "the cattle was rattled by the battery";
        System.out.println(replaceWords(dict, sentence));
    }
}

Line Notes

String[] words = sentence.split(" ");Split sentence into words

for (String word : words)Iterate over each word

String replacement = word;Initialize replacement as original word

for (String root : dictionary)Check all roots for prefix match

if (word.startsWith(root) && root.length() < replacement.length())Update replacement if root is shorter prefix

sb.append(replacement).append(" ");Append replaced word and space

return sb.toString().trim();Return final sentence without trailing space

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

string replaceWords(vector<string>& dictionary, string sentence) {
    vector<string> words;
    string word, result;
    for (int i = 0, n = sentence.size(); i <= n; ++i) {
        if (i == n || sentence[i] == ' ') {
            words.push_back(word);
            word = "";
        } else {
            word += sentence[i];
        }
    }
    for (auto& w : words) {
        string replacement = w;
        for (auto& root : dictionary) {
            if (w.compare(0, root.size(), root) == 0 && root.size() < replacement.size()) {
                replacement = root;
            }
        }
        result += replacement + " ";
    }
    if (!result.empty()) result.pop_back();
    return result;
}

int main() {
    vector<string> dict = {"cat", "bat", "rat"};
    string sentence = "the cattle was rattled by the battery";
    cout << replaceWords(dict, sentence) << endl;
    return 0;
}

Line Notes

for (int i = 0, n = sentence.size(); i <= n; ++i)Split sentence into words manually

words.push_back(word);Add completed word to list

for (auto& w : words)Iterate over each word

string replacement = w;Initialize replacement as original word

if (w.compare(0, root.size(), root) == 0 && root.size() < replacement.size())Check if root is prefix and shorter

result += replacement + " ";Append replaced word and space

if (!result.empty()) result.pop_back();Remove trailing space before returning

function replaceWords(dictionary, sentence) {
    const words = sentence.split(' ');
    const result = [];
    for (const word of words) {
        let replacement = word;
        for (const root of dictionary) {
            if (word.startsWith(root) && root.length < replacement.length) {
                replacement = root;
            }
        }
        result.push(replacement);
    }
    return result.join(' ');
}

// Test
const dict = ["cat", "bat", "rat"];
const sentence = "the cattle was rattled by the battery";
console.log(replaceWords(dict, sentence));

Line Notes

const words = sentence.split(' ');Split sentence into words

for (const word of words)Iterate over each word

let replacement = word;Initialize replacement as original word

for (const root of dictionary)Check all roots for prefix match

if (word.startsWith(root) && root.length < replacement.length)Update replacement if root is shorter prefix

result.push(replacement);Add replaced word to result array

return result.join(' ');Join replaced words into final sentence

⏱

Complexity

TimeO(m * n * k) where m = number of words in sentence, n = number of roots, k = average root length

SpaceO(m * k) for storing split words and result

For each word, we check all roots to find prefix matches, leading to a nested loop over words and roots. Prefix check is O(k).

💡 If sentence has 1000 words and dictionary 1000 roots, this approach does up to 1,000,000 prefix checks, which is slow.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

🧠

Sorting Roots + Prefix Checking

💡 Sorting roots by length allows early stopping when checking prefixes, improving efficiency over brute force but still not optimal.

Intuition

Sort roots by length ascending. For each word, check roots in order; the first root that is a prefix is the shortest replacement.

Algorithm

1. Sort the dictionary roots by length ascending.
2. Split the sentence into words.
3. For each word, iterate over sorted roots.
4. Replace the word with the first root that is a prefix.
5. If no root matches, keep the word.
6. Join all words back into a sentence.

💡 Sorting helps find shortest prefix quickly but still requires checking many roots for each word.

</>

Code

def replaceWords(dictionary, sentence):
    dictionary.sort(key=len)
    words = sentence.split()
    result = []
    for word in words:
        replacement = word
        for root in dictionary:
            if word.startswith(root):
                replacement = root
                break
        result.append(replacement)
    return ' '.join(result)

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

Line Notes

dictionary.sort(key=len)Sort roots by length to find shortest prefix first

words = sentence.split()Split sentence into words

for word in words:Process each word

for root in dictionary:Check roots in ascending length order

if word.startswith(root):If root is prefix, replace immediately

breakStop checking further roots once shortest prefix found

result.append(replacement)Add replaced word to result

return ' '.join(result)Reconstruct sentence

import java.util.*;
public class ReplaceWords {
    public static String replaceWords(List<String> dictionary, String sentence) {
        dictionary.sort(Comparator.comparingInt(String::length));
        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String word : words) {
            String replacement = word;
            for (String root : dictionary) {
                if (word.startsWith(root)) {
                    replacement = root;
                    break;
                }
            }
            sb.append(replacement).append(" ");
        }
        return sb.toString().trim();
    }

    public static void main(String[] args) {
        List<String> dict = Arrays.asList("cat", "bat", "rat");
        String sentence = "the cattle was rattled by the battery";
        System.out.println(replaceWords(dict, sentence));
    }
}

Line Notes

dictionary.sort(Comparator.comparingInt(String::length));Sort roots by length ascending

String[] words = sentence.split(" ");Split sentence into words

for (String word : words)Iterate over each word

for (String root : dictionary)Check roots in order

if (word.startsWith(root))If root is prefix, replace word

break;Stop checking once shortest prefix found

sb.append(replacement).append(" ");Append replaced word

return sb.toString().trim();Return final sentence

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

string replaceWords(vector<string>& dictionary, string sentence) {
    sort(dictionary.begin(), dictionary.end(), [](const string& a, const string& b) {
        return a.size() < b.size();
    });
    vector<string> words;
    string word, result;
    for (int i = 0, n = sentence.size(); i <= n; ++i) {
        if (i == n || sentence[i] == ' ') {
            words.push_back(word);
            word = "";
        } else {
            word += sentence[i];
        }
    }
    for (auto& w : words) {
        string replacement = w;
        for (auto& root : dictionary) {
            if (w.compare(0, root.size(), root) == 0) {
                replacement = root;
                break;
            }
        }
        result += replacement + " ";
    }
    if (!result.empty()) result.pop_back();
    return result;
}

int main() {
    vector<string> dict = {"cat", "bat", "rat"};
    string sentence = "the cattle was rattled by the battery";
    cout << replaceWords(dict, sentence) << endl;
    return 0;
}

Line Notes

sort(dictionary.begin(), dictionary.end(), [](const string& a, const string& b) {Sort roots by length ascending

for (int i = 0, n = sentence.size(); i <= n; ++i)Split sentence into words

words.push_back(word);Add word to list

for (auto& w : words)Iterate over each word

if (w.compare(0, root.size(), root) == 0)Check if root is prefix

replacement = root;Replace word with root

break;Stop checking further roots

result += replacement + " ";Append replaced word

function replaceWords(dictionary, sentence) {
    dictionary.sort((a, b) => a.length - b.length);
    const words = sentence.split(' ');
    const result = [];
    for (const word of words) {
        let replacement = word;
        for (const root of dictionary) {
            if (word.startsWith(root)) {
                replacement = root;
                break;
            }
        }
        result.push(replacement);
    }
    return result.join(' ');
}

// Test
const dict = ["cat", "bat", "rat"];
const sentence = "the cattle was rattled by the battery";
console.log(replaceWords(dict, sentence));

Line Notes

dictionary.sort((a, b) => a.length - b.length);Sort roots by length ascending

const words = sentence.split(' ');Split sentence into words

for (const word of words)Iterate over each word

for (const root of dictionary)Check roots in order

if (word.startsWith(root))If root is prefix, replace word

replacement = root;Update replacement

break;Stop checking further roots

result.push(replacement);Add replaced word to result

⏱

Complexity

TimeO(m * n * k) but often faster in practice due to early break

SpaceO(m * k) for words and result

Sorting roots helps find shortest prefix early, reducing checks per word but worst case still checks many roots.

💡 Sorting helps but still can be slow if dictionary is large; better data structures exist.

Interview Verdict: Accepted but not optimal for very large inputs

This approach improves over brute force but can still be slow; good stepping stone to trie solution.

🧠

Optimal Trie-Based Prefix Search

💡 Using a trie data structure allows efficient prefix searches by traversing characters, avoiding repeated string comparisons.

Intuition

Build a trie from the dictionary roots. For each word, traverse the trie character by character to find the shortest root prefix. Replace the word if found; else keep it.

Algorithm

1. Build a trie from all dictionary roots, marking end of root words.
2. Split the sentence into words.
3. For each word, traverse the trie character by character:
4. If a trie node marks end of a root, stop and use that prefix as replacement.
5. If traversal ends without match, keep the original word.
6. Join all replaced words into the final sentence.

💡 Trie traversal efficiently finds shortest prefix without checking all roots explicitly.

</>

Code

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

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

    def insert(self, word):
        node = self.root
        for char in word:
            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:
            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:
        trie.insert(root)
    words = sentence.split()
    result = []
    for word in words:
        prefix = trie.search_shortest_prefix(word)
        result.append(prefix if prefix else word)
    return ' '.join(result)

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

Line Notes

self.children = {}Dictionary to store child nodes for each character

self.is_end = FalseMarks if node represents end of a root word

def insert(self, word):Insert root into trie character by character

if char not in node.children:Create new node if character path missing

node.is_end = TrueMark end of root word

def search_shortest_prefix(self, word):Find shortest root prefix for given word

if node.is_end:Return prefix immediately when root end found

result.append(prefix if prefix else word)Replace word if prefix found, else original

import java.util.*;
class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}

class Trie {
    TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEnd = true;
    }

    public String searchShortestPrefix(String word) {
        TrieNode node = root;
        StringBuilder prefix = new StringBuilder();
        for (char c : word.toCharArray()) {
            if (!node.children.containsKey(c)) return null;
            node = node.children.get(c);
            prefix.append(c);
            if (node.isEnd) return prefix.toString();
        }
        return null;
    }
}

public class ReplaceWords {
    public static String replaceWords(List<String> dictionary, String sentence) {
        Trie trie = new Trie();
        for (String root : dictionary) trie.insert(root);
        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String word : words) {
            String prefix = trie.searchShortestPrefix(word);
            sb.append(prefix != null ? prefix : word).append(" ");
        }
        return sb.toString().trim();
    }

    public static void main(String[] args) {
        List<String> dict = Arrays.asList("cat", "bat", "rat");
        String sentence = "the cattle was rattled by the battery";
        System.out.println(replaceWords(dict, sentence));
    }
}

Line Notes

Map<Character, TrieNode> children = new HashMap<>();Stores child nodes for each character

boolean isEnd = false;Marks end of root word

node.children.putIfAbsent(c, new TrieNode());Create child node if missing

if (!node.children.containsKey(c)) return null;Stop if prefix path breaks

if (node.isEnd) return prefix.toString();Return prefix immediately when root end found

sb.append(prefix != null ? prefix : word).append(" ");Append replaced or original word

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

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c))
                node->children[c] = new TrieNode();
            node = node->children[c];
        }
        node->isEnd = true;
    }

    string searchShortestPrefix(const string& word) {
        TrieNode* node = root;
        string prefix;
        for (char c : word) {
            if (!node->children.count(c)) return "";
            node = node->children[c];
            prefix += c;
            if (node->isEnd) return prefix;
        }
        return "";
    }
};

string replaceWords(vector<string>& dictionary, string sentence) {
    Trie trie;
    for (auto& root : dictionary) trie.insert(root);
    vector<string> words;
    string word, result;
    for (int i = 0, n = sentence.size(); i <= n; ++i) {
        if (i == n || sentence[i] == ' ') {
            words.push_back(word);
            word = "";
        } else {
            word += sentence[i];
        }
    }
    for (auto& w : words) {
        string prefix = trie.searchShortestPrefix(w);
        result += (prefix.empty() ? w : prefix) + " ";
    }
    if (!result.empty()) result.pop_back();
    return result;
}

int main() {
    vector<string> dict = {"cat", "bat", "rat"};
    string sentence = "the cattle was rattled by the battery";
    cout << replaceWords(dict, sentence) << endl;
    return 0;
}

Line Notes

unordered_map<char, TrieNode*> children;Map child nodes by character

bool isEnd = false;Mark end of root word

if (!node->children.count(c))Create child node if missing

if (!node->children.count(c)) return "";Stop if prefix path breaks

if (node->isEnd) return prefix;Return prefix immediately when root end found

result += (prefix.empty() ? w : prefix) + " ";Append replaced or original word

class TrieNode {
    constructor() {
        this.children = new Map();
        this.isEnd = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) {
                node.children.set(char, new TrieNode());
            }
            node = node.children.get(char);
        }
        node.isEnd = true;
    }

    searchShortestPrefix(word) {
        let node = this.root;
        let prefix = '';
        for (const char of word) {
            if (!node.children.has(char)) return null;
            node = node.children.get(char);
            prefix += char;
            if (node.isEnd) return prefix;
        }
        return null;
    }
}

function replaceWords(dictionary, sentence) {
    const trie = new Trie();
    for (const root of dictionary) trie.insert(root);
    const words = sentence.split(' ');
    const result = [];
    for (const word of words) {
        const prefix = trie.searchShortestPrefix(word);
        result.push(prefix !== null ? prefix : word);
    }
    return result.join(' ');
}

// Test
const dict = ["cat", "bat", "rat"];
const sentence = "the cattle was rattled by the battery";
console.log(replaceWords(dict, sentence));

Line Notes

this.children = new Map();Map to store child nodes by character

this.isEnd = false;Mark end of root word

if (!node.children.has(char))Create child node if missing

if (!node.children.has(char)) return null;Stop if prefix path breaks

if (node.isEnd) return prefix;Return prefix immediately when root end found

result.push(prefix !== null ? prefix : word);Add replaced or original word

⏱

Complexity

TimeO(m * k) where m = number of words, k = average word length

SpaceO(n * l) for trie storage where n = number of roots, l = average root length

Building trie takes O(n*l). Searching each word prefix is O(k). This is efficient for large inputs.

💡 Trie reduces repeated prefix checks by sharing common prefixes, making prefix search very fast.

Interview Verdict: Accepted and optimal for large inputs

This is the best approach to implement in interviews for prefix replacement problems.

📊

All Approaches - One-Glance Tradeoffs

💡 Trie approach is best for coding in interviews; brute force is only for explanation; sorting roots is intermediate.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m * n * k)	O(m * k)	No	N/A	Mention only - never code due to inefficiency
2. Sorting Roots + Prefix Checking	O(m * n * k) but often faster due to early break	O(m * k)	No	N/A	Good intermediate explanation, rarely coded
3. Trie-Based Prefix Search	O(m * k)	O(n * l)	No	Yes	Code this approach for optimal solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when to present each. Focus on trie approach for coding.

How to Present

Clarify problem requirements and constraints.Explain brute force approach and its inefficiency.Discuss sorting roots to improve brute force.Introduce trie data structure for optimal prefix search.Code the trie solution and test with examples.

Time Allocation

Clarify: 3min → Approach discussion: 5min → Code trie: 10min → Test & optimize: 7min. Total ~25min

What the Interviewer Tests

Ability to identify prefix search pattern, knowledge of trie data structure, and optimization skills.

Common Follow-ups

• What if dictionary is very large? → Trie still efficient, consider memory tradeoffs.
• Can you optimize space? → Use array instead of map for fixed alphabet.

💡 Follow-ups test understanding of trie tradeoffs and memory optimization.

🔍

Pattern Recognition

When to Use

1) Need to find shortest prefix from dictionary for words, 2) Dictionary contains many roots, 3) Sentence has many words, 4) Efficiency matters

Signature Phrases

replace words with shortest rootprefix dictionary lookup

NOT This Pattern When

Problems requiring substring matching or suffix trees are different patterns.

Similar Problems

Implement Trie (Prefix Tree) - foundational for prefix searchesLongest Word in Dictionary - uses trie to find longest prefixReplace Words with Prefixes - variant of this problem

Practice

1. Consider the following Python code implementing the trie + DFS approach to find index pairs of substrings matching words. Given text = "abcab" and words = ["ab", "bc", "ca"], what is the final sorted list res returned by indexPairs(text, words)?

easy

A. [[0,1],[1,2],[3,4]]

B. [[0,1],[1,2],[2,3]]

C. [[0,1],[2,3],[3,4]]

D. [[0,1],[1,2],[2,3],[3,4]]

Solution

1. Step 1: Build the trie from words ["ab", "bc", "ca"]

   The trie has branches for 'a'->'b', 'b'->'c', and 'c'->'a', each marking word_end at the last character.

2. Step 2: DFS from each index in text "abcab"

   From index 0: 'a'->'b' matches "ab" -> [0,1]. From index 1: 'b'->'c' matches "bc" -> [1,2]. From index 2: 'c'->'a' matches "ca" -> [2,3]. From index 3: 'a'->'b' matches "ab" -> [3,4]. From index 4: 'b' no further match.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All four pairs found and sorted correctly [OK]

Hint: Trace DFS from each index carefully [OK]

Common Mistakes:

• Missing last match at index 3
• Off-by-one in end index

2. Consider the following code snippet implementing the optimal trie-based solution for shortest unique prefixes. Given the input words = ["dog", "dove", "duck"], what is the output of shortest_unique_prefix(words)?

easy

A. ["do", "dov", "du"]

B. ["d", "dov", "du"]

C. ["dog", "dove", "duck"]

D. ["dog", "dov", "du"]

Solution

1. Step 1: Trace insertion frequencies

   Insert "dog": d(1), o(1), g(1); "dove": d(2), o(2), v(1), e(1); "duck": d(3), u(1), c(1), k(1).

2. Step 2: Find unique prefixes

   For "dog": prefix "dog" (g freq=1) unique; for "dove": prefix "dov" (v freq=1) unique; for "duck": prefix "du" (u freq=1) unique.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefixes match first node with freq=1 [OK]

Hint: Unique prefix ends where node freq equals 1 [OK]

Common Mistakes:

• Stopping prefix too early
• Assuming first letter always unique

3. Consider the following buggy code snippet for checking concatenated words. Which line contains the subtle bug that causes false positives by counting a word as concatenated by itself?

medium

A. Line 6: Recursive call increments count incorrectly

B. Line 4: Loop range includes len(word)+1 causing index error

C. Line 5: Using prefix slicing incorrectly

D. Line 2: Base case condition allowing count >= 1

Solution

1. Step 1: Analyze base case condition for concatenation count

   Base case returns True if count >= 1, which allows a single word to be considered concatenated by itself.

2. Step 2: Correct condition should require at least two words concatenated

   Changing to count >= 2 ensures only words formed by two or more shorter words return True.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bug causes false positives by counting the word itself as concatenated [OK]

Hint: Base case must require at least two words concatenated [OK]

Common Mistakes:

• Allowing count >= 1 in base case
• Off-by-one in loop ranges

4. Examine the following buggy code snippet for palindrome pairs using Trie + DFS. Which line contains the subtle bug that causes missing pairs involving empty strings?

medium

A. No special handling for empty string in add_word or search

B. Line checking is_palindrome(word[:len(word)-i]) in add_word

C. Line checking if node.index >= 0 and node.index != index in search

D. Line setting node.index = index after insertion

Solution

1. Step 1: Identify empty string edge case

   Empty string pairs with palindromes require special handling to add pairs involving empty string indices.

2. Step 2: Check code for empty string handling

   Neither add_word nor search explicitly handle empty string cases, causing missing pairs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Empty string handling is a known subtle bug [OK]

Hint: Empty string pairs require explicit checks [OK]

Common Mistakes:

• Assuming palindrome checks cover empty strings
• Missing empty string special case
• Confusing index assignments

5. What is the time complexity of the optimal Word Break solution that uses iterative DP combined with a reversed trie for prefix checks, where n is the length of the string and m is the maximum length of words in the dictionary?

medium

A. O(n * log m) due to binary search in trie children

B. O(n^2) because of nested loops over the string

C. O(n * m) because for each position, trie traversal is bounded by max word length

D. O(n * m^2) because each trie traversal can take up to m steps and each step checks children

Solution

1. Step 1: Identify loops and trie traversal cost

   Outer loop runs n times. Inner loop traverses backwards up to m characters (max word length). Trie traversal per character is O(1) on average due to hashmap children.

2. Step 2: Combine to get total complexity

   Total time is O(n * m). Nested loops do not run n^2 because inner loop breaks early when no trie child exists.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie traversal bounded by max word length m [OK]

Hint: Trie traversal limits inner loop to max word length [OK]

Common Mistakes:

• Assuming inner loop always runs n times
• Confusing trie traversal cost with binary search
• Ignoring early breaks in inner loop