Formatted question description: https://leetcode.ca/all/1065.html

1065. Index Pairs of a String

Level

Easy

Description

Given a text string and words (a list of strings), return all index pairs [i, j] so that the substring text[i]...text[j] is in the list of words.

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].

Note:

1. All strings contains only lowercase English letters.
2. It’s guaranteed that all strings in words are different.
3. 1 <= text.length <= 100
4. 1 <= words.length <= 20
5. 1 <= words[i].length <= 50
6. Return the pairs [i,j] in sorted order (i.e. sort them by their first coordinate in case of ties sort them by their second coordinate).

Solution

For each word in words, find all occurrences of word in text, and add the index pairs to the result list. Sort the result list and return.

class Solution {
    public int[][] indexPairs(String text, String[] words) {
        List<int[]> indexPairsList = new ArrayList<int[]>();
        for (String word : words) {
            int wordLength = word.length();
            int curIndex = 0;
            while (curIndex >= 0) {
                curIndex = text.indexOf(word, curIndex);
                if (curIndex >= 0) {
                    indexPairsList.add(new int[]{curIndex, curIndex + wordLength - 1});
                    curIndex++;
                }
            }
        }
        Collections.sort(indexPairsList, new Comparator<int[]>() {
            public int compare(int[] array1, int[] array2) {
                if (array1[0] != array2[0])
                    return array1[0] - array2[0];
                else
                    return array1[1] - array2[1];
            }
        });
        int length = indexPairsList.size();
        int[][] indexPairs = new int[length][2];
        for (int i = 0; i < length; i++) {
            int[] indexPair = indexPairsList.get(i);
            indexPairs[i][0] = indexPair[0];
            indexPairs[i][1] = indexPair[1];
        }
        return indexPairs;
    }
}

All Problems

All Solutions