# 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:

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

## Examples

Example 1:

```python
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:

```python
[[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)

```python
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

```python
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 |