Index Pairs of a String
EasyUpdated: Aug 2, 2025
Practice on:
Problem
Given a string text and an array of strings words, return an array of all index pairs[i, j]so that the substringtext[i...j]is inwords.
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).
Examples
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.
Solution
Method 1 – Trie with Brute Force Search
Intuition
We want to efficiently find all substrings of text that match any word in words. A Trie allows us to quickly check for any word starting at each position in text.
Approach
- Build a Trie from all words in
words. - For each index
iintext, start fromiand traverse the Trie as long as characters match:- If a Trie node is marked as the end of a word, record the pair
[i, j]. - Continue until no further match is possible.
- If a Trie node is marked as the end of a word, record the pair
- Collect all pairs and sort them by the required order.
Code
C++
struct TrieNode {
TrieNode* nxt[26] = {};
bool end = false;
};
class Solution {
public:
vector<vector<int>> indexPairs(string text, vector<string>& words) {
TrieNode* root = new TrieNode();
for (auto& w : words) {
TrieNode* cur = root;
for (char c : w) {
int i = c - 'a';
if (!cur->nxt[i]) cur->nxt[i] = new TrieNode();
cur = cur->nxt[i];
}
cur->end = true;
}
vector<vector<int>> ans;
int n = text.size();
for (int i = 0; i < n; ++i) {
TrieNode* cur = root;
for (int j = i; j < n; ++j) {
int idx = text[j] - 'a';
if (!cur->nxt[idx]) break;
cur = cur->nxt[idx];
if (cur->end) ans.push_back({i, j});
}
}
return ans;
}
};
Go
type TrieNode struct {
nxt [26]*TrieNode
end bool
}
func indexPairs(text string, words []string) [][]int {
root := &TrieNode{}
for _, w := range words {
cur := root
for _, c := range w {
idx := c - 'a'
if cur.nxt[idx] == nil {
cur.nxt[idx] = &TrieNode{}
}
cur = cur.nxt[idx]
}
cur.end = true
}
var ans [][]int
n := len(text)
for i := 0; i < n; i++ {
cur := root
for j := i; j < n; j++ {
idx := text[j] - 'a'
if cur.nxt[idx] == nil {
break
}
cur = cur.nxt[idx]
if cur.end {
ans = append(ans, []int{i, j})
}
}
}
return ans
}
Java
class TrieNode {
TrieNode[] nxt = new TrieNode[26];
boolean end = false;
}
class Solution {
public int[][] indexPairs(String text, String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode cur = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (cur.nxt[i] == null) cur.nxt[i] = new TrieNode();
cur = cur.nxt[i];
}
cur.end = true;
}
List<int[]> ans = new ArrayList<>();
int n = text.length();
for (int i = 0; i < n; ++i) {
TrieNode cur = root;
for (int j = i; j < n; ++j) {
int idx = text.charAt(j) - 'a';
if (cur.nxt[idx] == null) break;
cur = cur.nxt[idx];
if (cur.end) ans.add(new int[]{i, j});
}
}
return ans.toArray(new int[0][]);
}
}
Kotlin
class TrieNode {
val nxt = Array<TrieNode?>(26) { null }
var end = false
}
class Solution {
fun indexPairs(text: String, words: Array<String>): Array<IntArray> {
val root = TrieNode()
for (w in words) {
var cur = root
for (c in w) {
val i = c - 'a'
if (cur.nxt[i] == null) cur.nxt[i] = TrieNode()
cur = cur.nxt[i]!!
}
cur.end = true
}
val ans = mutableListOf<IntArray>()
val n = text.length
for (i in 0 until n) {
var cur = root
for (j in i until n) {
val idx = text[j] - 'a'
if (cur.nxt[idx] == null) break
cur = cur.nxt[idx]!!
if (cur.end) ans.add(intArrayOf(i, j))
}
}
return ans.toTypedArray()
}
}
Python
class TrieNode:
def __init__(self):
self.nxt = [None] * 26
self.end = False
class Solution:
def indexPairs(self, text: str, words: list[str]) -> list[list[int]]:
root = TrieNode()
for w in words:
cur = root
for c in w:
i = ord(c) - ord('a')
if not cur.nxt[i]:
cur.nxt[i] = TrieNode()
cur = cur.nxt[i]
cur.end = True
ans = []
n = len(text)
for i in range(n):
cur = root
for j in range(i, n):
idx = ord(text[j]) - ord('a')
if not cur.nxt[idx]:
break
cur = cur.nxt[idx]
if cur.end:
ans.append([i, j])
return ans
Rust
struct TrieNode {
nxt: [Option<Box<TrieNode>>; 26],
end: bool,
}
impl TrieNode {
fn new() -> Self {
Self { nxt: Default::default(), end: false }
}
}
fn index_pairs(text: &str, words: Vec<&str>) -> Vec<(usize, usize)> {
let root = Box::new(TrieNode::new());
for w in words {
let mut cur = &root;
for c in w.chars() {
let i = (c as u8 - b'a') as usize;
cur = cur.nxt[i].get_or_insert_with(|| Box::new(TrieNode::new()));
}
cur.end = true;
}
let n = text.len();
let text = text.as_bytes();
let mut ans = vec![];
for i in 0..n {
let mut cur = &root;
for j in i..n {
let idx = (text[j] - b'a') as usize;
if cur.nxt[idx].is_none() { break; }
cur = cur.nxt[idx].as_ref().unwrap();
if cur.end { ans.push((i, j)); }
}
}
ans
}
TypeScript
class TrieNode {
nxt: (TrieNode | null)[] = Array(26).fill(null);
end = false;
}
class Solution {
indexPairs(text: string, words: string[]): number[][] {
const root = new TrieNode();
for (const w of words) {
let cur = root;
for (const c of w) {
const i = c.charCodeAt(0) - 97;
if (!cur.nxt[i]) cur.nxt[i] = new TrieNode();
cur = cur.nxt[i]!;
}
cur.end = true;
}
const ans: number[][] = [];
const n = text.length;
for (let i = 0; i < n; ++i) {
let cur = root;
for (let j = i; j < n; ++j) {
const idx = text.charCodeAt(j) - 97;
if (!cur.nxt[idx]) break;
cur = cur.nxt[idx]!;
if (cur.end) ans.push([i, j]);
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n * L)— n is the length of text, L is the sum of all word lengths (since we may traverse up to the length of the longest word for each position). - 🧺 Space complexity:
O(L)— For the Trie, where L is the total length of all words.