Index Pairs of a String solution and explanation
7 more videos on this problem
Leetcode 1065 Index Pairs of a StringRen Zhang · 17:48 · 2K views
Leetcode - Solving "Index Pairs of a String"Joseph Weidinger · 11:27 · 630 views
1065. Index Pairs of a String - Week 1/5 Leetcode May ChallengeProgramming Live with Larry · 4:31 · 471 views
1065. Index Pairs of a StringBit Mouse (bitmouse) · 5:35 · 464 views
猩猩的乐园 Leetcode 1065 Index Pairs of a String猩猩的乐园 · 11:08 · 259 views
LeetCode 1065 | Index Pairs of a String | HashSet | BF | JavaSleepy Cracker · 8:04 · 168 views
LeetCode 1065: Index Pairs of a String — The String Trick (C#)DSA Mastery Lab · 3:26 · 1 view
LeetCode 1065: Index Pairs of a StringAlitaCode · 26:44 · 1 view
The problem
Given a string text and an array of strings words, return an array of all index pairs [i, j] so that the substring text[i...j] is in words.
Return the pairs [i, j] in sorted order (i.e., sort them by their first coordinate, and in case of ties sort them by their second coordinate).
Example 1:
Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"] Output: [[3,7],[9,13],[10,17]]
Example 2:
Input: text = "ababa", words = ["aba","ab"] Output: [[0,1],[0,2],[2,3],[2,4]] Explanation: Notice that matches can overlap, see "aba" is found in [0,2] and [2,4].
Constraints:
1 <= text.length <= 1001 <= words.length <= 201 <= words[i].length <= 50textandwords[i]consist of lowercase English letters.- All the strings of
wordsare unique.
Approach overview
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.
Solution
class Solution:
def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
words = set(words)
n = len(text)
return [
[i, j] for i in range(n) for j in range(i, n) if text[i : j + 1] in words
]class Trie {
Trie[] children = new Trie[26];
boolean isEnd = false;
void insert(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
c -= 'a';
if (node.children[c] == null) {
node.children[c] = new Trie();
}
node = node.children[c];
}
node.isEnd = true;
}
}
class Solution {
public int[][] indexPairs(String text, String[] words) {
Trie trie = new Trie();
for (String w : words) {
trie.insert(w);
}
int n = text.length();
List<int[]> ans = new ArrayList<>();
for (int i = 0; i < n; ++i) {
Trie node = trie;
for (int j = i; j < n; ++j) {
int idx = text.charAt(j) - 'a';
if (node.children[idx] == null) {
break;
}
node = node.children[idx];
if (node.isEnd) {
ans.add(new int[] {i, j});
}
}
}
return ans.toArray(new int[ans.size()][2]);
}
}class Trie {
public:
vector<Trie*> children;
bool isEnd = false;
Trie() {
children.resize(26);
}
void insert(string word) {
Trie* node = this;
for (char c : word) {
c -= 'a';
if (!node->children[c]) node->children[c] = new Trie();
node = node->children[c];
}
node->isEnd = true;
}
};
class Solution {
public:
vector<vector<int>> indexPairs(string text, vector<string>& words) {
Trie* trie = new Trie();
for (auto w : words) trie->insert(w);
int n = text.size();
vector<vector<int>> ans;
for (int i = 0; i < n; ++i) {
Trie* node = trie;
for (int j = i; j < n; ++j) {
int idx = text[j] - 'a';
if (!node->children[idx]) break;
node = node->children[idx];
if (node->isEnd) ans.push_back({i, j});
}
}
return ans;
}
};type Trie struct {
children [26]*Trie
isEnd bool
}
func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(word string) {
node := this
for _, c := range word {
idx := int(c - 'a')
if node.children[idx] == nil {
node.children[idx] = newTrie()
}
node = node.children[idx]
}
node.isEnd = true
}
func indexPairs(text string, words []string) [][]int {
trie := newTrie()
for _, w := range words {
trie.insert(w)
}
n := len(text)
var ans [][]int
for i := range text {
node := trie
for j := i; j < n; j++ {
idx := int(text[j] - 'a')
if node.children[idx] == nil {
break
}
node = node.children[idx]
if node.isEnd {
ans = append(ans, []int{i, j})
}
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Hash Set | O(n * m * k) | O(m * k) | Small dictionary size or quick prototype solution |
| Trie-Based Matching | O(n * L) | O(T) | Best general solution when many words share prefixes |
| Sorted Words + Binary Search | O(n * log m * L) | O(m) | When dictionary is static and prefix checks rely on sorted lookup |
Frequently asked questions
Is Index Pairs of a String easy or hard?
LeetCode classifies this problem as Easy. The brute force solution is straightforward, but recognizing that a Trie can reduce redundant substring checks demonstrates stronger understanding of string algorithms.
Index Pairs of a String Python/Java solution
In Python or Java, the standard implementation builds a Trie from the words list and scans the text from each index. Whenever a Trie node marks the end of a word, the algorithm records the pair [start, end]. The same logic translates easily to C++ and Go with similar complexity.
How to solve Index Pairs of a String in O(n)?
Strict O(n) is not achievable because each starting index may need to explore multiple characters. The closest optimal solution is O(n * L) using a Trie. From each index in the text, traverse the Trie until the prefix no longer matches or the maximum word length is reached.
What is the best approach for Index Pairs of a String?
The Trie-based approach is the most efficient and commonly expected solution. Insert all words into a Trie, then scan the text from every starting index while traversing the Trie. Each successful word match produces an index pair. This method runs in O(n * L) time where L is the maximum word length.
Is Index Pairs of a String asked at Google/Amazon/Meta?
This problem represents a common string matching pattern frequently seen in interviews at companies like Amazon and Google. Variations of multi-pattern matching using Trie structures or prefix checks appear in many real interview questions.
What data structure is used in Index Pairs of a String?
The most important data structure for the optimal solution is a Trie. The Trie allows efficient prefix matching against multiple dictionary words simultaneously. Arrays or lists store the final index pairs, and strings are traversed character by character during matching.
What is the time complexity of Index Pairs of a String?
The optimal Trie solution runs in O(n * L) time, where n is the length of the text and L is the maximum word length. Building the Trie takes O(T) where T is the total number of characters across all words. Space complexity is also O(T) for storing the Trie nodes.