Index Pairs of a String
Easy · Tries · Array · String · Trie · Sorting
Problem
You are given a string text and a list of distinct strings words.
Return every index pair [i, j] such that text[i..j] (both ends included) is one of the strings in words. Order the pairs by their first index, and pairs with the same first index by their second index. Occurrences may overlap.
Examples
Input: text = "banana", words = ["ana","nan","b"] Output: [[0,0],[1,3],[2,4],[3,5]]
"b" is at [0,0], "ana" occurs twice with overlap at [1,3] and [3,5], and "nan" is at [2,4].
Input: text = "aaa", words = ["a","aa"] Output: [[0,0],[0,1],[1,1],[1,2],[2,2]]
Every single "a" and every adjacent pair match. Pairs with the same start are ordered by their end.
Input: text = "hello", words = ["world"] Output: []
"world" does not occur in "hello".
Constraints
- 1 <= len(text) <= 100
- 1 <= len(words) <= 20
- 1 <= len(words[i]) <= 50
- text and words[i] consist of lowercase English letters
- All strings in words are distinct
Approaches
- Baseline: look up every substring in a set — time O(n³), space O(W)
Follow-up
With a long text and many words, walking from every start can still cost len(text) × longest word. The Aho-Corasick automaton adds failure links to the trie so a single left-to-right pass finds every occurrence, in time linear in the text plus the number of matches.
Related problems
Start free on Cariara · Coding problems · System design studio
