Index Pairs of a String

🎯

Index Pairs of a String

easyTRIEAmazonGoogle

Imagine you have a dictionary of words and a long text. You want to find all occurrences of any dictionary word inside the text, along with their start and end positions.

💡 This problem is about efficiently finding all substrings in a string that match any word from a given list. Beginners often struggle because naive substring checks are expensive, and understanding how tries help reduce redundant checks is key.

📋

Problem Statement

Given a string text and a list of words, return all index pairs [i, j] so that the substring text[i..j] is in words. Return the pairs sorted in ascending order by i, then j.

1 ≤ text.length ≤ 10^51 ≤ words.length ≤ 10^41 ≤ words[i].length ≤ 100text and words[i] consist of lowercase English letters only

💡

Example

Input"text = \"thestoryofleetcodeandme\", words = [\"story\",\"fleet\",\"leetcode\"]"

Output[[3,7],[9,13],[10,17]]

The substrings "story" (indices 3-7), "fleet" (9-13), and "leetcode" (10-17) appear in text.

• Empty words list → output is empty list
• Words not present in text → output is empty list
• Words that overlap in text → all valid pairs included
• Text with repeated characters and words → all occurrences found

⚠️

Common Mistakes

Checking substrings without using a set or trie

Leads to TLE on large inputs

✅ Use a set for O(1) lookup or build a trie to avoid repeated checks

Not sorting the output pairs before returning

Output order does not match expected, causing wrong answer

✅ Sort the result list by start index, then end index

Not handling overlapping matches correctly

Misses some valid pairs or duplicates pairs

✅ Collect all matches found during trie traversal or DFS without skipping

Using substring extraction inside nested loops inefficiently

Extra overhead slows down solution

✅ Use trie traversal to avoid repeated substring extraction

Forgetting to check if current trie node is a word end during traversal

Misses valid matches, incomplete results

✅ Check word_end flag at every step and record pairs accordingly

🧠

Brute Force (Nested Loops Checking Each Substring)

💡 This approach exists to build intuition by directly checking every possible substring against the word list, showing why naive methods are inefficient.

Intuition

Check every substring of text and see if it is in the words list by direct comparison.

Algorithm

1. For each start index i in text:
2. For each end index j from i to end of text:
3. Extract substring text[i..j]
4. Check if substring is in words list; if yes, add [i, j] to result

💡 The nested loops generate all substrings, which is easy to understand but costly because many substrings are checked repeatedly.

</>

Code

def indexPairs(text, words):
    res = []
    word_set = set(words)
    n = len(text)
    for i in range(n):
        for j in range(i, n):
            if text[i:j+1] in word_set:
                res.append([i, j])
    res.sort()
    return res

# Example usage
if __name__ == '__main__':
    text = "thestoryofleetcodeandme"
    words = ["story","fleet","leetcode"]
    print(indexPairs(text, words))

Line Notes

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

for i in range(n)Outer loop picks start index of substring

for j in range(i, n)Inner loop picks end index of substring

if text[i:j+1] in word_setCheck if current substring is a word

res.append([i, j])Add the valid index pair to results

res.sort()Sort results by start then end indices before returning

return resReturn the sorted list of index pairs

import java.util.*;
public class Solution {
    public List<List<Integer>> indexPairs(String text, String[] words) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        List<List<Integer>> res = new ArrayList<>();
        int n = text.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = text.substring(i, j + 1);
                if (wordSet.contains(sub)) {
                    res.add(Arrays.asList(i, j));
                }
            }
        }
        res.sort((a, b) -> a.get(0) != b.get(0) ? a.get(0) - b.get(0) : a.get(1) - b.get(1));
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String text = "thestoryofleetcodeandme";
        String[] words = {"story","fleet","leetcode"};
        System.out.println(sol.indexPairs(text, words));
    }
}

Line Notes

Set<String> wordSet = new HashSet<>(Arrays.asList(words))Use HashSet for fast membership checks

for (int i = 0; i < n; i++)Outer loop selects substring start

for (int j = i; j < n; j++)Inner loop selects substring end

String sub = text.substring(i, j + 1)Extract substring from i to j

if (wordSet.contains(sub))Check if substring is in words

res.add(Arrays.asList(i, j))Add valid index pair to results

res.sort(...)Sort pairs by start then end indices

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

class Solution {
public:
    vector<vector<int>> indexPairs(string text, vector<string>& words) {
        unordered_set<string> wordSet(words.begin(), words.end());
        vector<vector<int>> res;
        int n = text.size();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                string sub = text.substr(i, j - i + 1);
                if (wordSet.count(sub)) {
                    res.push_back({i, j});
                }
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};

int main() {
    Solution sol;
    string text = "thestoryofleetcodeandme";
    vector<string> words = {"story","fleet","leetcode"};
    vector<vector<int>> res = sol.indexPairs(text, words);
    for (auto &p : res) {
        cout << "[" << p[0] << "," << p[1] << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

unordered_set<string> wordSet(words.begin(), words.end())Hash set for O(1) substring membership

for (int i = 0; i < n; i++)Start index loop

for (int j = i; j < n; j++)End index loop

string sub = text.substr(i, j - i + 1)Extract substring from i to j

if (wordSet.count(sub))Check if substring is in words

res.push_back({i, j})Add valid index pair to results

sort(res.begin(), res.end())Sort pairs by start then end indices

var indexPairs = function(text, words) {
    const wordSet = new Set(words);
    const res = [];
    const n = text.length;
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            const sub = text.substring(i, j + 1);
            if (wordSet.has(sub)) {
                res.push([i, j]);
            }
        }
    }
    res.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    return res;
};

// Example usage
console.log(indexPairs("thestoryofleetcodeandme", ["story","fleet","leetcode"]));

Line Notes

const wordSet = new Set(words)Use Set for O(1) membership checks

for (let i = 0; i < n; i++)Outer loop for substring start

for (let j = i; j < n; j++)Inner loop for substring end

const sub = text.substring(i, j + 1)Extract substring from i to j

if (wordSet.has(sub))Check if substring is in words

res.push([i, j])Add valid index pair to results

res.sort(...)Sort results by start then end indices

⏱

Complexity

TimeO(n^2 * m) where n = length of text, m = average length of words

SpaceO(w) for storing words in a set, plus O(k) for output pairs

We check all O(n^2) substrings, each substring check is O(m) due to substring extraction and hash lookup

💡 For n=1000, this means about 1,000,000 substring checks, which is too slow for large inputs.

Interview Verdict: TLE / Use only to introduce problem

This approach is too slow for large inputs but helps understand the problem and motivates better solutions.

🧠

Trie Construction + Search From Each Position

💡 This approach introduces tries to efficiently check multiple words simultaneously, reducing redundant substring checks.

Intuition

Build a trie of all words, then for each index in text, traverse the trie to find all words starting at that index.

Algorithm

1. Build a trie from the list of words
2. For each index i in text:
3. Traverse the trie following characters text[i], text[i+1], ...
4. Whenever a word end is reached in trie, record [i, current_index]

💡 The trie lets us share prefix checks, so we don't restart from scratch for each substring.

</>

Code

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

class Solution:
    def indexPairs(self, text, words):
        root = TrieNode()
        for w in words:
            node = root
            for c in w:
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
            node.word_end = True

        res = []
        n = len(text)
        for i in range(n):
            node = root
            for j in range(i, n):
                c = text[j]
                if c not in node.children:
                    break
                node = node.children[c]
                if node.word_end:
                    res.append([i, j])
        res.sort()
        return res

# Example usage
if __name__ == '__main__':
    sol = Solution()
    text = "thestoryofleetcodeandme"
    words = ["story","fleet","leetcode"]
    print(sol.indexPairs(text, words))

Line Notes

class TrieNode:Define trie node structure

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

for w in wordsInsert each word into the trie

for i in range(n)Start searching from each index in text

if node.word_endIf current trie node marks end of a word, record the index pair

res.sort()Sort results before returning

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

public class Solution {
    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.wordEnd = true;
    }

    public List<List<Integer>> indexPairs(String text, String[] words) {
        for (String w : words) insert(w);
        List<List<Integer>> res = new ArrayList<>();
        int n = text.length();
        for (int i = 0; i < n; i++) {
            TrieNode node = root;
            for (int j = i; j < n; j++) {
                char c = text.charAt(j);
                if (!node.children.containsKey(c)) break;
                node = node.children.get(c);
                if (node.wordEnd) res.add(Arrays.asList(i, j));
            }
        }
        res.sort((a,b) -> a.get(0) != b.get(0) ? a.get(0)-b.get(0) : a.get(1)-b.get(1));
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String text = "thestoryofleetcodeandme";
        String[] words = {"story","fleet","leetcode"};
        System.out.println(sol.indexPairs(text, words));
    }
}

Line Notes

class TrieNodeDefine trie node with children map and word end flag

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

for (int i = 0; i < n; i++)Start search from each text index

if (node.wordEnd)Check if current node marks a word end

res.sort(...)Sort results by start then end indices

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

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

class Solution {
    TrieNode* root = new TrieNode();
public:
    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->wordEnd = true;
    }

    vector<vector<int>> indexPairs(string text, vector<string>& words) {
        for (auto& w : words) insert(w);
        vector<vector<int>> res;
        int n = text.size();
        for (int i = 0; i < n; i++) {
            TrieNode* node = root;
            for (int j = i; j < n; j++) {
                char c = text[j];
                if (!node->children.count(c)) break;
                node = node->children[c];
                if (node->wordEnd) res.push_back({i, j});
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};

int main() {
    Solution sol;
    string text = "thestoryofleetcodeandme";
    vector<string> words = {"story","fleet","leetcode"};
    vector<vector<int>> res = sol.indexPairs(text, words);
    for (auto &p : res) {
        cout << "[" << p[0] << "," << p[1] << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

struct TrieNodeDefine trie node with children map and word end flag

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

for (int i = 0; i < n; i++)Start search from each index

if (node->wordEnd)Record pair when word ends here

sort(res.begin(), res.end())Sort pairs by start then end indices

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

var indexPairs = function(text, words) {
    const root = new TrieNode();
    for (const w of words) {
        let node = root;
        for (const c of w) {
            if (!node.children.has(c)) node.children.set(c, new TrieNode());
            node = node.children.get(c);
        }
        node.wordEnd = true;
    }

    const res = [];
    const n = text.length;
    for (let i = 0; i < n; i++) {
        let node = root;
        for (let j = i; j < n; j++) {
            const c = text[j];
            if (!node.children.has(c)) break;
            node = node.children.get(c);
            if (node.wordEnd) res.push([i, j]);
        }
    }
    res.sort((a,b) => a[0] - b[0] || a[1] - b[1]);
    return res;
};

// Example usage
console.log(indexPairs("thestoryofleetcodeandme", ["story","fleet","leetcode"]));

Line Notes

class TrieNodeDefine trie node with children map and word end flag

if (!node.children.has(c))Add child node if missing

for (let i = 0; i < n; i++)Start search from each index

if (node.wordEnd)Add pair when word ends here

res.sort(...)Sort pairs by start then end indices

⏱

Complexity

TimeO(n * m) where n = length of text, m = max length of words

SpaceO(w * m) for trie storage, w = number of words

Building trie takes O(w*m). Searching from each index takes O(n*m) in worst case.

💡 For n=100000 and max word length 100, this is feasible and much faster than brute force.

Interview Verdict: Accepted / Efficient for large inputs

This approach balances clarity and efficiency, making it a strong interview solution.

🧠

Trie + DFS with Early Pruning and Result Collection

💡 This approach refines the previous by explicitly using DFS/backtracking on the trie to find all matches starting at each index, emphasizing backtracking skills.

Intuition

Use DFS from each text index to traverse trie nodes, collecting all word ends found along the path.

Algorithm

1. Build a trie from words
2. For each index i in text, call DFS starting at root and index i
3. In DFS, if current node is word end, record [start, current_index]
4. Recurse to child nodes matching next character in text until no match

💡 DFS allows clean recursive exploration of all possible matches starting at each index, with pruning when no child matches.

</>

Code

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

class Solution:
    def indexPairs(self, text, words):
        root = TrieNode()
        for w in words:
            node = root
            for c in w:
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
            node.word_end = True

        res = []
        n = len(text)

        def dfs(node, i, start):
            if node.word_end:
                res.append([start, i-1])
            if i == n:
                return
            c = text[i]
            if c in node.children:
                dfs(node.children[c], i+1, start)

        for i in range(n):
            dfs(root, i, i)

        res.sort()
        return res

# Example usage
if __name__ == '__main__':
    sol = Solution()
    text = "thestoryofleetcodeandme"
    words = ["story","fleet","leetcode"]
    print(sol.indexPairs(text, words))

Line Notes

def dfs(node, i, start)Recursive DFS to explore trie from index i

if node.word_endRecord pair when word ends at current node

if i == n: returnStop recursion if end of text reached

if c in node.childrenRecurse only if next character matches a child

for i in range(n)Start DFS from each index in text

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

public class Solution {
    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.wordEnd = true;
    }

    public void dfs(String text, int i, int start, TrieNode node, List<List<Integer>> res) {
        if (node.wordEnd) res.add(Arrays.asList(start, i - 1));
        if (i == text.length()) return;
        char c = text.charAt(i);
        if (node.children.containsKey(c)) {
            dfs(text, i + 1, start, node.children.get(c), res);
        }
    }

    public List<List<Integer>> indexPairs(String text, String[] words) {
        for (String w : words) insert(w);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < text.length(); i++) {
            dfs(text, i, i, root, res);
        }
        res.sort((a,b) -> a.get(0) != b.get(0) ? a.get(0)-b.get(0) : a.get(1)-b.get(1));
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String text = "thestoryofleetcodeandme";
        String[] words = {"story","fleet","leetcode"};
        System.out.println(sol.indexPairs(text, words));
    }
}

Line Notes

public void dfs(...)Recursive DFS method to explore trie matches

if (node.wordEnd)Add pair when word ends at current node

if (i == text.length()) returnStop recursion at end of text

if (node.children.containsKey(c))Recurse only if next char matches child

for (int i = 0; i < text.length(); i++)Start DFS from each index

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

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

class Solution {
    TrieNode* root = new TrieNode();
public:
    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->wordEnd = true;
    }

    void dfs(const string& text, int i, int start, TrieNode* node, vector<vector<int>>& res) {
        if (node->wordEnd) res.push_back({start, i - 1});
        if (i == (int)text.size()) return;
        char c = text[i];
        if (node->children.count(c)) {
            dfs(text, i + 1, start, node->children[c], res);
        }
    }

    vector<vector<int>> indexPairs(string text, vector<string>& words) {
        for (auto& w : words) insert(w);
        vector<vector<int>> res;
        for (int i = 0; i < (int)text.size(); i++) {
            dfs(text, i, i, root, res);
        }
        sort(res.begin(), res.end());
        return res;
    }
};

int main() {
    Solution sol;
    string text = "thestoryofleetcodeandme";
    vector<string> words = {"story","fleet","leetcode"};
    vector<vector<int>> res = sol.indexPairs(text, words);
    for (auto &p : res) {
        cout << "[" << p[0] << "," << p[1] << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

void dfs(...)Recursive DFS to find all matches starting at index

if (node->wordEnd)Record pair when word ends here

if (i == (int)text.size()) returnStop recursion at text end

if (node->children.count(c))Recurse only if next char matches child

for (int i = 0; i < (int)text.size(); i++)Start DFS from each index

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

var indexPairs = function(text, words) {
    const root = new TrieNode();
    for (const w of words) {
        let node = root;
        for (const c of w) {
            if (!node.children.has(c)) node.children.set(c, new TrieNode());
            node = node.children.get(c);
        }
        node.wordEnd = true;
    }

    const res = [];
    const n = text.length;

    function dfs(node, i, start) {
        if (node.wordEnd) res.push([start, i - 1]);
        if (i === n) return;
        const c = text[i];
        if (node.children.has(c)) {
            dfs(node.children.get(c), i + 1, start);
        }
    }

    for (let i = 0; i < n; i++) {
        dfs(root, i, i);
    }

    res.sort((a,b) => a[0] - b[0] || a[1] - b[1]);
    return res;
};

// Example usage
console.log(indexPairs("thestoryofleetcodeandme", ["story","fleet","leetcode"]));

Line Notes

function dfs(node, i, start)Recursive DFS to explore trie matches

if (node.wordEnd)Add pair when word ends at current node

if (i === n) returnStop recursion at end of text

if (node.children.has(c))Recurse only if next char matches child

for (let i = 0; i < n; i++)Start DFS from each index

⏱

Complexity

TimeO(n * m) where n = length of text, m = max length of words

SpaceO(w * m) for trie storage, w = number of words

DFS explores trie paths from each index, pruning early when no match, so worst case similar to approach 2.

💡 This approach is a clean recursive way to find matches, useful to demonstrate backtracking skills.

Interview Verdict: Accepted / Clean recursive solution

This approach is elegant and shows mastery of trie traversal and recursion, good for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, approach 2 (Trie + Search) is the best balance of clarity and efficiency to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2 * m)	O(w)	No	N/A	Mention only - never code
2. Trie Construction + Search From Each Position	O(n * m)	O(w * m)	No	Yes	Code this approach in most interviews
3. Trie + DFS Backtracking	O(n * m)	O(w * m)	Yes (deep recursion if words very long)	Yes	Good for demonstrating recursion and backtracking

💼

Interview Strategy

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

How to Present

Clarify problem constraints and examplesState brute force approach and its inefficiencyIntroduce trie to optimize substring checksExplain trie construction and search from each positionOptionally show DFS backtracking for clarityDiscuss time and space complexityWrite clean code and test edge cases

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of substring search, trie data structure, optimization from brute force, and clean code implementation.

Common Follow-ups

• What if words are very long? → Trie still efficient, but max word length affects search time
• Can we use Aho-Corasick automaton? → Yes, for even faster multi-pattern matching

💡 Follow-ups test your knowledge of advanced string matching algorithms and scalability considerations.

🔍

Pattern Recognition

When to Use

1) Need to find multiple words in a text; 2) Words share prefixes; 3) Need all occurrences, not just one; 4) Efficiency matters beyond brute force

Signature Phrases

all index pairssubstring text[i..j]words list

NOT This Pattern When

Single pattern substring search (use KMP or Rabin-Karp), or problems only needing existence of one word

Similar Problems

Word Search II - uses trie + backtracking to find multiple words in a gridImplement Trie (Prefix Tree) - foundational trie construction and searchSubstring with Concatenation of All Words - substring matching with multiple words

Practice

1. Consider the following Python code implementing the bitwise trie approach to find maximum XOR of two numbers. Given the input nums = [2, 5], what is the value of current_xor after processing the number 5 in the second loop?

easy

A. 3

B. 6

C. 7

D. 5

Solution

1. Step 1: Trace bits of number 5

   5 in binary (32-bit) ends with bits ...00000101. We check bits from 31 down to 0.

2. Step 2: Traverse trie to maximize XOR

   For each bit, we try to go to the opposite bit in trie. For 5, the best XOR partner is 2 (binary 10). XOR of 5 and 2 is 7, so current_xor accumulates bits where toggled bit exists, resulting in 7.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Maximum XOR of 2 and 5 is 7, which matches current_xor after processing 5 [OK]

Hint: XOR bits accumulate where opposite bit exists [OK]

Common Mistakes:

• Confusing final max_xor with current_xor at iteration

2. What is the time complexity of the optimal bitwise trie approach to count pairs with XOR in a range for an input array of size n and maximum number M (max element)?

medium

A. O(n * log M)

B. O(n^2)

C. O(n * M)

D. O(n * log n)

Solution

1. Step 1: Identify operations per element

   Each number is inserted into the trie in O(log M) time, where M is the max number (bit length).

2. Step 2: Query per element also takes O(log M)

   For each number, querying the trie for counts less than a limit also takes O(log M).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(n * log M) due to insert and query per element [OK]

Hint: Trie operations scale with bit length, not array size squared [OK]

Common Mistakes:

• Assuming O(n^2) due to pairs
• Confusing M with n in complexity
• Ignoring log factor from bit length

3. What is the worst-case time complexity of searching for a word of length m in a trie implemented with a hash map for children, assuming the alphabet size is large and the trie contains n words?

medium

A. O(m) because each character leads to a hash map lookup

B. O(m * log n) due to hash map lookup cost increasing with n

C. O(n * m) because each search may scan all words

D. O(m * |alphabet|) because each character requires scanning all children

Solution

1. Step 1: Identify search steps in trie

   Search traverses nodes for each character in the word, performing a hash map lookup per character.

2. Step 2: Analyze hash map lookup cost

   Hash map lookup is O(1) average, so total time is O(m) where m is word length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Search time depends on word length, not number of stored words [OK]

Hint: Trie search time depends on word length, not number of words [OK]

Common Mistakes:

• Confusing trie search with scanning all words (O(n*m))

4. Suppose the WordDictionary is extended to support searching for words with the wildcard '*' that matches zero or more characters (instead of '.' matching exactly one). Which of the following modifications to the trie search algorithm correctly handles '*' wildcard searches?

hard

A. Use recursion or stack to explore zero or more characters by branching at current node and advancing index accordingly.

B. Treat '*' as '.' and continue with single character branching only.

C. Precompute all possible expansions of '*' and store them in the trie during addWord.

D. Ignore '*' and treat it as a literal character during search.

Solution

1. Step 1: Understand '*' wildcard semantics

   '*' matches zero or more characters, so search must explore skipping '*' or consuming characters.

2. Step 2: Identify correct search strategy

   Using recursion or stack to explore both skipping '*' (index+1) and consuming children (index unchanged) correctly handles zero or more matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Branching on both skipping and consuming characters handles '*' wildcard [OK]

Hint: '*' requires branching on skip or consume [OK]

Common Mistakes:

• Treating '*' like '.'
• Precomputing expansions is infeasible
• Ignoring '*' wildcard semantics

5. Suppose the problem changes: you want to find the maximum XOR of two numbers in an array, but now numbers can be negative 32-bit integers. Which modification to the bitwise trie approach is necessary to handle negative numbers correctly?

hard

A. Use two's complement 32-bit representation and treat bits as unsigned during trie insertion and traversal

B. Ignore sign bit and only build trie from absolute values of numbers

C. Use 64-bit representation to store numbers in trie to avoid sign issues

D. Preprocess numbers by adding a large constant to make all numbers positive before building trie

Solution

1. Step 1: Understand representation of negative numbers

   Negative integers in 32-bit are stored in two's complement form, which can be treated as unsigned bit patterns for trie operations.

2. Step 2: Modify trie insertion and traversal

   Insert and traverse bits as unsigned 32-bit integers, including the sign bit, to correctly handle negative numbers.

3. Step 3: Avoid incorrect approaches

   Using 64-bit or adding constants changes problem semantics; ignoring sign bit loses information.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Two's complement allows uniform bitwise trie handling of negative numbers [OK]

Hint: Two's complement bits can be treated as unsigned [OK]

Common Mistakes:

• Ignoring sign bit or converting to absolute values