Index Pairs of a String

Return all pairs [start, end] (inclusive) such that the substring text[start:end + 1] is one of the words. Sort the pairs by start, then by end. A pair appears once even if the word is in the list twice.

For text = "thestoryofleetcodeandme" and words = ["story", "fleet", "leetcode"] the answer is [[3, 7], [9, 13], [10, 17]].

The starter code checks every word at every position. It is correct but too slow for many words.

Examples

Example 1

Input:

index_pairs('thestoryofleetcodeandme', ['story', 'fleet', 'leetcode'])

Output:

[[3, 7], [9, 13], [10, 17]]

Example 2

Input:

index_pairs('ababa', ['aba', 'ab'])

Output:

[[0, 1], [0, 2], [2, 3], [2, 4]]

Constraints

• 0 <= len(text) <= 100000
• 0 <= len(words) <= 2000
• 1 <= len(word) <= 10, lower-case letters.