Code Implementation

class Solution:
    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
        res = []
        for word in words:
            start = text.find(word)
            while start != -1:
                res.append([start, start + len(word) - 1])
                start = text.find(word, start + 1)
        res.sort()
        return res
      

class Solution {
public:
    vector<vector<int>> indexPairs(string text, vector<string>& words) {
        vector<vector<int>> res;
        for (const string& word : words) {
            size_t pos = text.find(word, 0);
            while (pos != string::npos) {
                res.push_back({(int)pos, (int)(pos + word.size() - 1)});
                pos = text.find(word, pos + 1);
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};
      

class Solution {
    public int[][] indexPairs(String text, String[] words) {
        List<int[]> res = new ArrayList<>();
        for (String word : words) {
            int idx = text.indexOf(word);
            while (idx != -1) {
                res.add(new int[]{idx, idx + word.length() - 1});
                idx = text.indexOf(word, idx + 1);
            }
        }
        res.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int[][] ans = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) ans[i] = res.get(i);
        return ans;
    }
}
      

var indexPairs = function(text, words) {
    let res = [];
    for (let word of words) {
        let idx = text.indexOf(word);
        while (idx !== -1) {
            res.push([idx, idx + word.length - 1]);
            idx = text.indexOf(word, idx + 1);
        }
    }
    res.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    return res;
};
      

Problem Description

Given a string text and an array of strings words, your task is to find all pairs of indices [i, j] such that the substring text[i..j] is exactly equal to one of the words in words. You should return all such pairs in lexicographical order (sorted by i, then j).

• Each pair [i, j] must represent a valid substring in text.
• You may have multiple pairs for the same word if it appears multiple times.
• Do not reuse the same indices for overlapping substrings unless they match different words or occurrences.
• Return the result as a list of pairs, sorted as specified.

Thought Process

To solve this problem, the first idea that comes to mind is brute-force: for every possible substring of text, check if it matches any word in words. However, this is inefficient, especially for long texts and many words.

We can optimize by reversing the loop: for each word in words, search for all its occurrences in text. This way, we avoid generating all substrings and only look for exact matches. Searching for a word in a string can be done efficiently using built-in functions like find or indexOf. We repeat this for each word, collecting all starting and ending indices.

After collecting all pairs, we sort them to ensure lexicographical order. This approach is much faster in practice and easy to implement.

Solution Approach

• Step 1: Initialize an empty result list to store index pairs.
• Step 2: For each word in words:
  • Use a string search function (like find or indexOf) to find the first occurrence of the word in text.
  • While you find occurrences:
    • Record the starting index i and ending index j = i + len(word) - 1.
    • Continue searching for the next occurrence, starting after the current one.
• Step 3: After processing all words, sort the list of pairs by their starting and ending indices.
• Step 4: Return the sorted list as the answer.

This approach leverages efficient substring search and avoids unnecessary work by only considering exact matches.

Example Walkthrough

Suppose text = "ababa" and words = ["aba", "ab"].

1. For the word "aba":
   • First occurrence at index 0: substring text[0:3] = "aba" → pair [0,2].
   • Next occurrence at index 2: substring text[2:5] = "aba" → pair [2,4].
2. For the word "ab":
   • First occurrence at index 0: substring text[0:2] = "ab" → pair [0,1].
   • Next occurrence at index 2: substring text[2:4] = "ab" → pair [2,3].
3. Collect all pairs: [[0,2], [2,4], [0,1], [2,3]].
4. Sort them: [[0,1], [0,2], [2,3], [2,4]].

The final output is [[0,1], [0,2], [2,3], [2,4]].

Time and Space Complexity

• Brute-force approach:
  • Time: O(N^2 * M), where N is the length of text and M is the number of words, since you check all substrings.
  • Space: O(K) for the result, where K is the number of pairs found.
• Optimized approach (as above):
  • Time: O(W * (L + O)) where W is the number of words, L is the length of text, and O is the number of occurrences of each word (since find or indexOf scans text for each word).
  • Sorting the pairs takes O(K \log K) where K is the number of pairs found.
  • Space: O(K) for the result list.

In practice, this is much more efficient than brute-force, especially if words contains short strings.

Summary

The key insight is to search for each word in the text, rather than generating all substrings. This reduces unnecessary computation and leverages fast substring search. By collecting all index pairs and sorting them, we fulfill the problem's requirements efficiently and elegantly. This approach is simple, avoids brute-force, and is easy to implement in most programming languages.