Problem statement

https://leetcode.com/problems/index-pairs-of-a-string/

Solution

One way to solve this problem is just to check all substrings of text and check if we have them in our words

Complexity

It is O(n^3) for time and O(M) for space where M is total length of words in words.

Remark

Another solution is for each wor to check all possible places with complexity O(M*n).

Finally, there is trie solution, where we can put all words to trie in O(M) time and then we start with every one of n elements in text and traverse our tree: total complexity will be O(M + n*k), where k is the longest word.

Code

class Solution:
    def indexPairs(self, text, words):
        words_set, ans = set(words), []
        for i, j in combinations(range(len(text) + 1), 2):
            if text[i:j] in words_set:
                ans += [[i, j-1]]
                
        return ans