LeetCode 1065: Index Pairs of a String

Problem Restatement

We are given a string text and a list of strings words.

Return all [i, j] pairs such that the substring text[i:j+1] is in words.

The result must be sorted by i, then by j.

The official constraints state that 1 <= text.length <= 100 and 1 <= words.length <= 20.

Input and Output

Item	Meaning
Input	String `text` and list `words`
Output	Sorted list of `[i, j]` pairs where `text[i:j+1]` is in `words`

Function shape:

def indexPairs(text: str, words: list[str]) -> list[list[int]]:
    ...

Examples

Example 1:

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

"story" appears at [3,7], and "leetcode" appears at [10,17]. The word "fleet" does not appear, so it contributes no interval.

Answer:

[[3,7],[10,17]]

Key Insight

Since the text and word list are small, we can simply check every starting position and every word.

Alternatively, build a trie of all words and for each starting position in the text, traverse the trie.

Implementation (Simple)

class Solution:
    def indexPairs(self, text: str, words: list[str]) -> list[list[int]]:
        word_set = set(words)
        result = []
        n = len(text)

        for i in range(n):
            for j in range(i, n):
                if text[i:j+1] in word_set:
                    result.append([i, j])

        return result

Testing

def run_tests():
    s = Solution()

    assert s.indexPairs("thestoryofleetcodeandme", ["story","fleet","leetcode"]) == [[3,7],[10,17]]
    assert s.indexPairs("ababa", ["aba","ab"]) == [[0,1],[0,2],[2,3],[2,4]]
    assert s.indexPairs("aaaa", ["aa","aa"]) == [[0,1],[1,2],[2,3]]

    print("all tests passed")

run_tests()

Test	Expected	Why
Long text	`[[3,7],[10,17]]`	Two words found
Overlapping words	`[[0,1],[0,2],[2,3],[2,4]]`	Both `"ab"` and `"aba"` found at multiple positions