Index Pairs of a String - Solution & Explanation

Problem Overview: You are given a string text and a list of words. The goal is to return all index pairs [i, j] such that the substring text[i...j] exists in the words list. The result must be sorted first by the starting index and then by the ending index.

Approach 1: Brute Force Substring Check (Time: O(n * m * k), Space: O(m * k))

The most direct solution checks every possible substring starting at each index of text. Store all words in a hash set for O(1) lookups. For each start index i, extend the substring character by character and check whether the current substring exists in the set. If it does, record the pair [i, j]. Here, n is the length of the text, m is the number of words, and k is the average word length. This approach is simple and works well when the word list is small, but repeated substring creation makes it inefficient for larger inputs. The solution mainly relies on operations over string processing and simple array traversal.

Approach 2: Trie-Based Prefix Matching (Time: O(n * L), Space: O(T))

A more efficient approach builds a Trie from all words in the dictionary. Each node represents a character and marks whether a word ends at that node. After building the Trie, iterate through the text starting at every index i. From that position, traverse the Trie while moving forward in the text. If a node representing the current prefix marks the end of a word, record the index pair [i, j]. Stop early if the current character does not exist in the Trie path.

This avoids generating every substring explicitly and instead matches prefixes incrementally. If L is the maximum word length, each starting index explores at most L characters, giving a time complexity of O(n * L). The Trie requires O(T) space where T is the total number of characters across all words. This approach is a classic application of the Trie data structure for multi-pattern matching. The output pairs are naturally generated in sorted order because you scan the text left-to-right and extend matches forward.

Approach 3: Sorted Words with Prefix Checks (Time: O(n * log m * L), Space: O(m))

Another option sorts the word list and checks prefixes using binary search. For each index in the text, you test substrings up to the maximum word length and check whether they exist in the sorted list. Sorting allows faster lookups compared to scanning the entire dictionary, but prefix checks still require substring construction. This method leverages sorting and binary search but is typically slower than the Trie approach for large dictionaries.

Recommended for interviews: The Trie-based solution is what interviewers usually expect. The brute force approach demonstrates that you understand the problem and can generate candidate substrings. Building a Trie shows stronger algorithmic thinking because it reduces redundant work and performs prefix matching efficiently across many words.