Longest Word in Dictionary

🎯

Longest Word in Dictionary

mediumTRIEGoogleAmazon

Imagine you have a dictionary of words and want to find the longest word such that every prefix of that word is also a valid word in the dictionary. This is like finding the tallest building where every floor below is fully constructed.

💡 This problem tests your understanding of prefix relationships between words. Beginners often struggle because they try to check prefixes inefficiently or miss the requirement that all prefixes must exist as words, which is naturally suited for a Trie data structure.

📋

Problem Statement

Given an array of strings words representing an English dictionary, return the longest word in words such that every prefix of it is also in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order. If no answer exists, return an empty string.

1 ≤ words.length ≤ 10^51 ≤ words[i].length ≤ 30words[i] consists of lowercase English letters.

💡

Example

Input"[\"w\",\"wo\",\"wor\",\"worl\",\"world\"]"

Output"world"

All prefixes of "world" ("w", "wo", "wor", "worl") are in the list, so "world" is the longest valid word.

Input"[\"a\", \"banana\", \"app\", \"appl\", \"ap\", \"apply\", \"apple\"]"

Output"apple"

"apple" is the longest word where all prefixes "a", "ap", "app", "appl" exist in the list.

• Empty input array → output is empty string
• All words are single letters → output is lex smallest letter
• Multiple words with same length and valid prefixes → output lex smallest
• Words with prefixes missing → output empty string

⚠️

Common Mistakes

Not checking all prefixes for each word

Incorrect output because some words with missing prefixes are considered valid

✅ Ensure every prefix of a word exists before accepting it

Not sorting words before prefix set approach

Lexicographically smaller word might be missed when lengths tie

✅ Sort words lexicographically before processing

In Trie BFS, enqueueing nodes without complete words

Invalid prefixes get included, breaking the prefix condition

✅ Only enqueue child nodes that mark complete words

Using substring operations inside nested loops inefficiently

Causes time limit exceeded on large inputs

✅ Use Trie or sorting + set to optimize prefix checks

Not handling empty input or single-letter words

Code may crash or return incorrect results

✅ Add checks for empty input and handle single-letter words properly

🧠

Brute Force (Check Prefixes for Each Word)

💡 This approach exists to build intuition by directly verifying the problem's condition without any data structure optimization. It helps understand the prefix requirement clearly.

Intuition

For each word, check if all its prefixes exist in the list by scanning the list repeatedly. Keep track of the longest valid word.

Algorithm

1. For each word in the list:
2. For each prefix of the word (from length 1 to word length - 1):
3. Check if the prefix exists in the list.
4. If all prefixes exist, update the longest valid word if needed.

💡 The nested loops make it hard to see efficiency, but this approach directly enforces the problem's prefix condition.

</>

Code

def longestWord(words):
    word_set = set(words)
    longest = ""
    for word in words:
        valid = True
        for i in range(1, len(word)):
            if word[:i] not in word_set:
                valid = False
                break
        if valid:
            if len(word) > len(longest) or (len(word) == len(longest) and word < longest):
                longest = word
    return longest

# Driver code
if __name__ == "__main__":
    words = ["w","wo","wor","worl","world"]
    print(longestWord(words))  # Output: world

Line Notes

word_set = set(words)Convert list to set for O(1) prefix existence checks

for word in words:Iterate over each candidate word

for i in range(1, len(word)):Check every prefix length of the current word

if word[:i] not in word_set:If any prefix missing, mark invalid and stop checking

if valid:Only consider words with all prefixes present

if len(word) > len(longest) or (len(word) == len(longest) and word < longest):Update longest word by length and lex order

import java.util.*;
public class Solution {
    public static String longestWord(String[] words) {
        Set<String> wordSet = new HashSet<>();
        for (String w : words) wordSet.add(w);
        String longest = "";
        for (String word : words) {
            boolean valid = true;
            for (int i = 1; i < word.length(); i++) {
                if (!wordSet.contains(word.substring(0, i))) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                if (word.length() > longest.length() || (word.length() == longest.length() && word.compareTo(longest) < 0)) {
                    longest = word;
                }
            }
        }
        return longest;
    }

    public static void main(String[] args) {
        String[] words = {"w","wo","wor","worl","world"};
        System.out.println(longestWord(words)); // Output: world
    }
}

Line Notes

Set<String> wordSet = new HashSet<>();Use HashSet for O(1) prefix lookups

for (String word : words) {Iterate over each word to check prefixes

for (int i = 1; i < word.length(); i++) {Check all prefixes of current word

if (!wordSet.contains(word.substring(0, i))) {If prefix missing, mark invalid

if (valid) {Only update longest if all prefixes exist

if (word.length() > longest.length() || (word.length() == longest.length() && word.compareTo(longest) < 0)) {Update longest word by length and lex order

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

string longestWord(vector<string>& words) {
    unordered_set<string> wordSet(words.begin(), words.end());
    string longest = "";
    for (auto& word : words) {
        bool valid = true;
        for (int i = 1; i < (int)word.size(); i++) {
            if (wordSet.find(word.substr(0, i)) == wordSet.end()) {
                valid = false;
                break;
            }
        }
        if (valid) {
            if ((int)word.size() > (int)longest.size() || ((int)word.size() == (int)longest.size() && word < longest)) {
                longest = word;
            }
        }
    }
    return longest;
}

int main() {
    vector<string> words = {"w","wo","wor","worl","world"};
    cout << longestWord(words) << endl; // Output: world
    return 0;
}

Line Notes

unordered_set<string> wordSet(words.begin(), words.end());Initialize hash set for O(1) prefix checks

for (auto& word : words) {Loop over each word to validate prefixes

for (int i = 1; i < (int)word.size(); i++) {Check every prefix of the word

if (wordSet.find(word.substr(0, i)) == wordSet.end()) {If prefix missing, mark invalid

if (valid) {Only update longest if all prefixes exist

if ((int)word.size() > (int)longest.size() || ((int)word.size() == (int)longest.size() && word < longest)) {Update longest word by length and lex order

function longestWord(words) {
    const wordSet = new Set(words);
    let longest = "";
    for (const word of words) {
        let valid = true;
        for (let i = 1; i < word.length; i++) {
            if (!wordSet.has(word.substring(0, i))) {
                valid = false;
                break;
            }
        }
        if (valid) {
            if (word.length > longest.length || (word.length === longest.length && word < longest)) {
                longest = word;
            }
        }
    }
    return longest;
}

// Test
console.log(longestWord(["w","wo","wor","worl","world"])); // Output: world

Line Notes

const wordSet = new Set(words);Create set for O(1) prefix existence checks

for (const word of words) {Iterate over each word to check prefixes

for (let i = 1; i < word.length; i++) {Check all prefixes of current word

if (!wordSet.has(word.substring(0, i))) {If prefix missing, mark invalid

if (valid) {Only update longest if all prefixes exist

if (word.length > longest.length || (word.length === longest.length && word < longest)) {Update longest word by length and lex order

⏱

Complexity

TimeO(n * m^2)

SpaceO(n * m)

For n words each of max length m, checking all prefixes (up to m) and substring operations cost O(m) each, resulting in O(n * m^2).

💡 For n=1000 and m=10, this means about 100,000 operations, which is slow but manageable for small inputs.

Interview Verdict: TLE on large inputs

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

🧠

Sorting + Prefix Checking with Set

💡 Sorting words lexicographically helps us check prefixes in order and prune invalid candidates early, improving efficiency over brute force.

Intuition

Sort words so prefixes come before longer words. Use a set to store valid words and only add a word if its prefix is already valid.

Algorithm

1. Sort the words lexicographically.
2. Initialize a set with an empty string to represent the base prefix.
3. Iterate over sorted words:
4. If the prefix (word without last char) is in the set, add the word to the set and update longest word if needed.

💡 Sorting ensures prefixes appear before their extensions, so we only add words whose prefixes are confirmed valid.

</>

Code

def longestWord(words):
    words.sort()
    valid = set([""])
    longest = ""
    for word in words:
        if word[:-1] in valid:
            valid.add(word)
            if len(word) > len(longest) or (len(word) == len(longest) and word < longest):
                longest = word
    return longest

# Driver code
if __name__ == "__main__":
    words = ["w","wo","wor","worl","world"]
    print(longestWord(words))  # Output: world

Line Notes

words.sort()Sort words lexicographically to ensure prefixes come first

valid = set([""])Initialize set with empty string as base prefix

if word[:-1] in valid:Check if prefix exists before adding word

valid.add(word)Add current word as valid if prefix exists

if len(word) > len(longest) or (len(word) == len(longest) and word < longest):Update longest word by length and lex order to handle ties

import java.util.*;
public class Solution {
    public static String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> valid = new HashSet<>();
        valid.add("");
        String longest = "";
        for (String word : words) {
            if (valid.contains(word.substring(0, word.length() - 1))) {
                valid.add(word);
                if (word.length() > longest.length() || (word.length() == longest.length() && word.compareTo(longest) < 0)) {
                    longest = word;
                }
            }
        }
        return longest;
    }

    public static void main(String[] args) {
        String[] words = {"w","wo","wor","worl","world"};
        System.out.println(longestWord(words)); // Output: world
    }
}

Line Notes

Arrays.sort(words);Sort words lexicographically to process prefixes first

Set<String> valid = new HashSet<>();Set to store valid words with all prefixes

valid.add("");Add empty string as base prefix

if (valid.contains(word.substring(0, word.length() - 1))) {Check if prefix exists before adding word

valid.add(word);Add current word as valid

if (word.length() > longest.length() || (word.length() == longest.length() && word.compareTo(longest) < 0)) {Update longest word by length and lex order to handle ties

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

string longestWord(vector<string>& words) {
    sort(words.begin(), words.end());
    unordered_set<string> valid({""});
    string longest = "";
    for (auto& word : words) {
        if (valid.find(word.substr(0, word.size() - 1)) != valid.end()) {
            valid.insert(word);
            if (word.size() > longest.size() || (word.size() == longest.size() && word < longest)) {
                longest = word;
            }
        }
    }
    return longest;
}

int main() {
    vector<string> words = {"w","wo","wor","worl","world"};
    cout << longestWord(words) << endl; // Output: world
    return 0;
}

Line Notes

sort(words.begin(), words.end());Sort words lexicographically for prefix order

unordered_set<string> valid({""});Initialize set with empty string as base prefix

if (valid.find(word.substr(0, word.size() - 1)) != valid.end()) {Check if prefix exists before adding word

valid.insert(word);Add current word as valid

if (word.size() > longest.size() || (word.size() == longest.size() && word < longest)) {Update longest word by length and lex order to handle ties

function longestWord(words) {
    words.sort();
    const valid = new Set([""]);
    let longest = "";
    for (const word of words) {
        if (valid.has(word.slice(0, -1))) {
            valid.add(word);
            if (word.length > longest.length || (word.length === longest.length && word < longest)) {
                longest = word;
            }
        }
    }
    return longest;
}

// Test
console.log(longestWord(["w","wo","wor","worl","world"])); // Output: world

Line Notes

words.sort();Sort words lexicographically to ensure prefix order

const valid = new Set([""]);Initialize set with empty string as base prefix

if (valid.has(word.slice(0, -1))) {Check if prefix exists before adding word

valid.add(word);Add current word as valid

if (word.length > longest.length || (word.length === longest.length && word < longest)) {Update longest word by length and lex order to handle ties

⏱

Complexity

TimeO(n log n * m)

SpaceO(n * m)

Sorting n words costs O(n log n * m) due to string comparisons, and prefix checks are O(1) with set. Overall faster than brute force.

💡 For n=100000 and m=30, sorting dominates but prefix checks are efficient, making this approach scalable.

Interview Verdict: Accepted

This approach is efficient and easy to implement, suitable for most interview scenarios.

🧠

Trie + BFS Traversal

💡 Using a Trie explicitly models prefix relationships and BFS traversal ensures we find the longest valid word with all prefixes present, optimizing prefix checks.

Intuition

Build a Trie from all words. Use BFS to traverse nodes only if the node marks a complete word, ensuring all prefixes exist. Track the longest word found.

Algorithm

1. Build a Trie inserting all words, marking nodes that end words.
2. Use a queue to perform BFS starting from root.
3. At each node, enqueue child nodes only if they mark complete words.
4. Track the longest word found during BFS traversal.

💡 BFS ensures we explore words level by level, guaranteeing prefixes exist before children are visited.

</>

Code

from collections import deque

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

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

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.word = word

def longestWord(words):
    trie = Trie()
    for word in words:
        trie.insert(word)
    queue = deque([trie.root])
    longest = ""
    while queue:
        node = queue.popleft()
        for ch in sorted(node.children.keys()):  # changed to normal lex order
            child = node.children[ch]
            if child.word is not None:
                queue.append(child)
                if len(child.word) > len(longest) or (len(child.word) == len(longest) and child.word < longest):
                    longest = child.word
    return longest

# Driver code
if __name__ == "__main__":
    words = ["w","wo","wor","worl","world"]
    print(longestWord(words))  # Output: world

Line Notes

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

self.word = NoneStore complete word at node if it ends here

for ch in word:Insert characters one by one into Trie

node.word = wordMark node as end of a word

queue = deque([trie.root])Start BFS from root node

for ch in sorted(node.children.keys()):Traverse children in lex order to ensure lex smallest word found first

if child.word is not None:Only enqueue nodes that mark complete words

if len(child.word) > len(longest) or (len(child.word) == len(longest) and child.word < longest):Update longest word by length and lex order

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    String word = null;
}

public class Solution {
    TrieNode root = new TrieNode();

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

    public String longestWord(String[] words) {
        for (String w : words) insert(w);
        Queue<TrieNode> queue = new LinkedList<>();
        queue.offer(root);
        String longest = "";
        while (!queue.isEmpty()) {
            TrieNode node = queue.poll();
            List<Character> keys = new ArrayList<>(node.children.keySet());
            Collections.sort(keys);  // changed to normal lex order
            for (char ch : keys) {
                TrieNode child = node.children.get(ch);
                if (child.word != null) {
                    queue.offer(child);
                    if (child.word.length() > longest.length() || (child.word.length() == longest.length() && child.word.compareTo(longest) < 0)) {
                        longest = child.word;
                    }
                }
            }
        }
        return longest;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] words = {"w","wo","wor","worl","world"};
        System.out.println(sol.longestWord(words)); // Output: world
    }
}

Line Notes

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

String word = null;Store complete word at node if it ends here

for (char ch : word.toCharArray()) {Insert characters one by one into Trie

node.word = word;Mark node as end of a word

Queue<TrieNode> queue = new LinkedList<>();Use queue for BFS traversal

Collections.sort(keys);Traverse children in lex order to ensure lex smallest word found first

if (child.word != null) {Only enqueue nodes that mark complete words

if (child.word.length() > longest.length() || (child.word.length() == longest.length() && child.word.compareTo(longest) < 0)) {Update longest word by length and lex order

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    string word = "";
};

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

string longestWord(vector<string>& words) {
    Trie trie;
    for (auto& w : words) trie.insert(w);
    queue<TrieNode*> q;
    q.push(trie.root);
    string longest = "";
    while (!q.empty()) {
        TrieNode* node = q.front(); q.pop();
        vector<char> keys;
        for (auto& p : node->children) keys.push_back(p.first);
        sort(keys.begin(), keys.end());  // changed to normal lex order
        for (char ch : keys) {
            TrieNode* child = node->children[ch];
            if (!child->word.empty()) {
                q.push(child);
                if (child->word.size() > longest.size() || (child->word.size() == longest.size() && child->word < longest)) {
                    longest = child->word;
                }
            }
        }
    }
    return longest;
}

int main() {
    vector<string> words = {"w","wo","wor","worl","world"};
    cout << longestWord(words) << endl; // Output: world
    return 0;
}

Line Notes

unordered_map<char, TrieNode*> children;Map to store child nodes for each character

string word = "";Store complete word at node if it ends here

for (char ch : word) {Insert characters one by one into Trie

node->word = word;Mark node as end of a word

queue<TrieNode*> q;Queue for BFS traversal

sort(keys.begin(), keys.end());Traverse children in lex order to ensure lex smallest word found first

if (!child->word.empty()) {Only enqueue nodes that mark complete words

if (child->word.size() > longest.size() || (child->word.size() == longest.size() && child->word < longest)) {Update longest word by length and lex order

class TrieNode {
    constructor() {
        this.children = new Map();
        this.word = null;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }
    insert(word) {
        let node = this.root;
        for (const ch of word) {
            if (!node.children.has(ch)) {
                node.children.set(ch, new TrieNode());
            }
            node = node.children.get(ch);
        }
        node.word = word;
    }
}

function longestWord(words) {
    const trie = new Trie();
    for (const w of words) trie.insert(w);
    const queue = [trie.root];
    let longest = "";
    while (queue.length > 0) {
        const node = queue.shift();
        const keys = Array.from(node.children.keys()).sort();  // changed to normal lex order
        for (const ch of keys) {
            const child = node.children.get(ch);
            if (child.word !== null) {
                queue.push(child);
                if (child.word.length > longest.length || (child.word.length === longest.length && child.word < longest)) {
                    longest = child.word;
                }
            }
        }
    }
    return longest;
}

// Test
console.log(longestWord(["w","wo","wor","worl","world"])); // Output: world

Line Notes

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

this.word = null;Store complete word at node if it ends here

for (const ch of word) {Insert characters one by one into Trie

node.word = word;Mark node as end of a word

const queue = [trie.root];Initialize queue for BFS traversal

const keys = Array.from(node.children.keys()).sort();Traverse children in lex order to ensure lex smallest word found first

if (child.word !== null) {Only enqueue nodes that mark complete words

if (child.word.length > longest.length || (child.word.length === longest.length && child.word < longest)) {Update longest word by length and lex order

⏱

Complexity

TimeO(n * m + n * 26)

SpaceO(n * m)

Building the Trie takes O(n*m). BFS visits nodes with words only, up to n nodes, each with up to 26 children.

💡 For n=100000 and m=30, this approach is efficient and scales well due to Trie structure and BFS pruning.

Interview Verdict: Accepted

This is the optimal approach for prefix-related problems, demonstrating mastery of Trie and BFS.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the sorting + prefix set approach is usually the best balance of simplicity and efficiency to code quickly.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * m^2)	O(n * m)	No	N/A	Mention only - never code due to inefficiency
2. Sorting + Prefix Set	O(n log n * m)	O(n * m)	No	N/A	Code this approach in 95% of interviews
3. Trie + BFS	O(n * m)	O(n * m)	No	Yes	Use if comfortable with Trie; optimal and impressive

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding of the prefix condition.Step 3: Improve to sorting + prefix set approach for efficiency.Step 4: Present the Trie + BFS approach as the optimal solution.Step 5: Code the chosen approach carefully, test with examples and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of prefix relationships, ability to optimize from brute force, and knowledge of Trie data structure and BFS traversal.

Common Follow-ups

• What if prefixes can be missing? → Return empty string or handle accordingly.
• How to modify to return all longest words? → Store all candidates during BFS or sorting.

💡 Follow-ups test your flexibility and deeper understanding of the problem constraints and output requirements.

🔍

Pattern Recognition

When to Use

1) Need to check prefixes of words; 2) All prefixes must exist; 3) Find longest word with prefix property; 4) Lexicographical order matters.

Signature Phrases

every prefix of it is also in wordslongest wordlexicographical order

NOT This Pattern When

Problems that only require substring checks or suffix trees are different patterns.

Similar Problems

Longest Common Prefix - related prefix conceptImplement Trie (Prefix Tree) - building block for this problemWord Break - prefix existence and segmentation

Practice

1. Given a string text and a list of words, you need to find all pairs of indices [i, j] such that the substring text[i:j+1] is in the list of words. Which approach guarantees an optimal solution in terms of time complexity when the list of words is large and words have varying lengths?

easy

A. Build a trie from the list of words and perform a DFS from each index in the text to find matching substrings.

B. Use dynamic programming to store whether substrings are in the word list and build results bottom-up.

C. Use a brute force nested loop to check every substring against the list of words directly.

D. Sort the list of words and use binary search to check each substring generated from the text.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding all substrings of text that match any word in a large list. Checking every substring against the list directly is expensive.

2. Step 2: Recognize the trie + DFS pattern

   Building a trie from the words allows prefix-based pruning. DFS from each index in text efficiently finds all matching substrings without redundant checks, guaranteeing optimal time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Trie + DFS prunes search space better than brute force or binary search [OK]

Hint: Trie + DFS prunes prefix search efficiently [OK]

Common Mistakes:

• Thinking brute force is efficient enough for large inputs

2. You need to design a system that receives a continuous stream of characters and must efficiently determine if any suffix of the stream matches a word from a given dictionary. Which algorithmic approach best guarantees optimal query time and memory usage?

easy

A. Build a trie of the reversed dictionary words and maintain a limited-length stream buffer to traverse the trie backwards on each query.

B. Use a brute force approach that checks all suffixes of the stream against the dictionary on every query.

C. Use a prefix trie of the dictionary words and scan the stream from the start to check for matches.

D. Apply dynamic programming to store all possible substrings of the stream and check membership in the dictionary.

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking if any suffix of the stream matches a dictionary word efficiently, which suggests suffix-based matching.

2. Step 2: Evaluate approaches

   Brute force checking all suffixes is too slow. Prefix tries do not help with suffix matching. Dynamic programming for all substrings is inefficient. Building a trie of reversed words and traversing it backwards with a limited buffer optimizes both time and space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Reversed trie + limited buffer matches suffixes efficiently [OK]

Hint: Suffix matching needs reversed trie traversal [OK]

Common Mistakes:

• Using prefix trie for suffix matching
• Checking all suffixes brute force
• Using DP on all substrings

3. Suppose you want to extend the Trie to support deletion of words. Which of the following approaches correctly handles deletion without breaking prefix searches for other words?

hard

A. Remove the isEnd flag at the last node of the word and delete nodes bottom-up only if they have no children and isEnd is false

B. Delete all nodes corresponding to the word immediately, regardless of children

C. Set isEnd to false at the last node but never delete any nodes

D. Rebuild the entire trie after each deletion to remove unused nodes

Solution

1. Step 1: Understand deletion impact

   Removing isEnd flag marks word as deleted. Nodes can be deleted only if they are not prefixes of other words.

2. Step 2: Delete nodes bottom-up conditionally

   Delete nodes only if they have no children and isEnd is false to avoid breaking other words.

3. Step 3: Avoid unsafe deletions

   Deleting nodes immediately or rebuilding trie is inefficient or breaks other words.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Conditional bottom-up deletion preserves trie correctness [OK]

Hint: Delete nodes only if no children and isEnd is false [OK]

Common Mistakes:

• Deleting nodes without checking children breaks other words

4. Suppose the problem is modified so that words can be reused multiple times in overlapping substrings, and you want to find all index pairs including overlapping matches. Which modification to the trie + DFS approach correctly handles this scenario?

hard

A. Stop DFS immediately after finding a word_end to avoid duplicates.

B. Continue DFS after finding a word_end to find longer overlapping matches starting at the same index.

C. Use a set to store results and skip DFS calls if the substring was already found.

D. Build a suffix trie instead of a prefix trie to handle overlapping matches.

Solution

1. Step 1: Understand overlapping matches requirement

   Words can overlap and be reused, so after finding a word_end, DFS must continue to find longer matches starting at the same index.

2. Step 2: Modify DFS to continue after word_end

   Do not return immediately after appending a match; continue DFS to explore longer substrings that may also be words.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Continuing DFS ensures all overlapping matches are found [OK]

Hint: Don't stop DFS at first word_end for overlapping matches [OK]

Common Mistakes:

• Stopping DFS early loses longer or overlapping matches

5. Suppose the Word Break problem is modified so that dictionary words can be reused unlimited times in the segmentation. Which modification to the algorithm is necessary to correctly handle this variant?

hard

A. Modify the inner loop to continue checking all prefixes even after dp[i] is set to True

B. Change dp array to count number of ways instead of boolean flags

C. Remove the dp array and use pure recursion with memoization only

D. No change needed; the original DP with trie approach already supports reuse

Solution

1. Step 1: Understand reuse impact on DP

   When reuse is allowed, multiple segmentations can overlap. The DP must consider all possible prefixes, not stop at first True.

2. Step 2: Modify inner loop behavior

   Breaking early when dp[i] is True prevents exploring all segmentations. Removing the break allows full exploration, correctly handling reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing all prefixes ensures reuse is handled [OK]

Hint: Breaking early blocks multiple reuse paths [OK]

Common Mistakes:

• Assuming original DP supports reuse without change
• Changing dp to count ways unnecessarily
• Removing dp and relying on recursion only