1065. Index Pairs of a String

Problem Description

This problem asks for a function that, given a string text and an array of strings words, finds all substrings within text that match any of the strings in words. For each match, the function should return the starting and ending indices of the substring in the text. The output should consist of an array of index pairs [i, j], where text[i...j] (inclusive) is a substring found in the words list.

For example, if text = "dogcat" and words = ["cat", "dog"], the function should return [[0, 2], [3, 5]] since text[0...2] is "dog" and text[3...5] is "cat".

The output array should be sorted first by the starting index i and then by the ending index j in the case of a tie.

Intuition

The intuitive approach to solving this problem involves checking each possible substring of text against all words in the words list to see if there is a match. However, this naive approach would be inefficient as it would require a comparison of possibly every substring of text with every word in words, resulting in a potentially high time complexity.

To optimize, we can use a Trie data structure. A Trie is a type of search tree, an ordered data structure used to store a dynamic set of strings. It allows us to efficiently search for a string in a fixed set of strings, which is particularly useful for dealing with problems involving a dictionary of words (such as autocomplete features).

The idea is to first insert all the words from the words list into the Trie. Each node in the Trie represents a character from 'a' to 'z'. A node will have a flag is_end to denote whether the node represents the end of a word in the Trie.

Then, for each possible starting index i in the text, we will try to find any word in the words list that starts with text[i]. We do this by walking through the Trie tree with the characters in text starting from i. If we find a null child before reaching the end of a word, this means there's no match starting from this character, and we continue to the next starting index in text. If the node's is_end is true, then we found a word in words that matches the substring starting at i, and we add the current pair of indices [i, j] to our answers list.

This approach is much faster than comparing each substring, especially when there are many words in words or when words contain long strings.

Learn more about Trie and Sorting patterns.

Solution Approach

The solution employs a Trie data structure to optimize the process of searching for words within the text. Here's how the implementation works:

1. A Trie class is defined, which includes an array called children of length 26, to account for every letter of the English alphabet, and a boolean is_end that signifies whether a node corresponds to the end of a word in the Trie.

2. An insert method is added to the Trie class, allowing the insertion of a word into the Trie. This method is important because it sets up the Trie so that the indexPairs function can efficiently search for substrings later. The insert method works as follows:

   • For every character in the word to be inserted, it calculates the index of the character, assuming 'a' is at index 0 (using ord(c) - ord('a')).
   • It checks if there is already a child node for that character; if not, it creates a new Trie node at the respective index.
   • It then proceeds to the next character in the word until all characters are inserted.
   • After inserting the last character of the word, it marks that node as an end node by setting is_end to True.

3. In the Solution class, the indexPairs method is used to find all index pairs from the text that match any word within the words list by utilizing the Trie with the following steps:

   • First, for each word in words, the method insert is called to create the Trie representation of the words list.
   • An empty list ans is initialized to store the index pairs that will be the output of this function.
   • The function then iterates through every possible starting index i in text.
   • For each starting index i, the function attempts to form words by checking subsequent characters until either a word is found or an invalid (null) Trie path is encountered:
     • For each character text[j] starting from index i, the function calculates its index in the Trie.
     • If the Trie does not have a child node corresponding to text[j], meaning no word starts with the substring text[i...j], the loop breaks.
     • If the current Trie node signals the end of a word (node.is_end is True), we've found a complete word, and the indices [i, j] are added to the ans list.
   • Once all possible start indices i are tested, the method returns the filled-in ans list containing all matching index pairs.

This solution is efficient as it uses the Trie to quickly skip over non-matching substrings of text and recognizes the end of words without needing to check the words list for each substring explicitly.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Assume we have the following text and words:

1text = "themanevent"
2words = ["man", "event", "the"]

We want to find all substrings in text that match any of the words in words. The expected output is the index pairs that correspond to these substrings. For the given example, the expected output would be [[0, 2], [3, 5], [6, 10]] because:

• text[0...2] corresponds to "the".
• text[3...5] corresponds to "man".
• text[6...10] corresponds to "event".

Here is how the solution approach works step by step:

1. Create Trie: We start by constructing a Trie and inserting all the words from words into it.

   Trie after Insertion:

   1root
   2 |
   3 t - h - e - (end)
   4 |
   5 m - a - n - (end)
   6            |
   7            e - v - e - n - t - (end)

   • Each letter represents a node pointing to its children.
   • "(end)" signifies a complete word at that node.

2. Search for Substrings:

   • We check each starting index i in text.
   • Initialize ans as [], to store our results.

   For i=0 ("t" of "themanevent"):

   • We traverse the Trie. "the" is in the words list, so we add [0, 2] to ans.

   For i=1 ("h" of "hemanevent"):

   • "h" does not start any word by itself, so we do not add anything to ans.

   For i=2 ("e" of "emanevent"):

   • There is no word starting with "e" directly (only as a part of other words), so no indices are added to ans.

   For i=3 ("m" of "manevent"):

   • "man" is a word, so we add [3, 5] to ans.

   For i=4 and onwards:

   • Repeat above steps for each index until the end of text is reached.
   • When i=6, "event" is found, so we add [6, 10] to ans.

3. Result: After testing all indices, our ans is [[0, 2], [3, 5], [6, 10]], which we then return.

This method allows us to efficiently find all index pairs corresponding to words within the text using the Trie without having to check every possible substring against all words in words. By leveraging the Trie's structure, where each path down the Trie represents a potential word, we quickly identify substrings without exhaustive searching.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code is comprised of two parts: (1) Building the Trie, and (2) Searching for words in the text using the Trie.

1. Building the Trie:

   • Each word from the words list is inserted into the Trie.
   • If we assume the average length of a word in words is L, and there are W words, then the complexity for building the Trie is O(W * L).

2. Searching in text using the Trie:

   • For each position i in the text of length N, a check in the Trie is initiated.
   • In the worst case, each check can go up to the length of the text (N), if all characters are part of words in the Trie.
   • This nested loop results in a complexity of O(N^2) in the worst case.

Combining both parts, we have the worst-case time complexity as O(W * L + N^2).

Space Complexity

The space complexity is also composed of two parts: the space required for the Trie and the space required for the answer list.

1. Trie Space:

   • The Trie has at most 26 * W * L nodes (26 possible children for each character of each word). However, due to the sharing of common prefixes, the actual space will often be much less.
   • The worst-case space complexity for the Trie is O(26 * W * L).

2. Answer List Space:

   • In the worst case, every substring of text starting at i could be a word in Trie, so this could be as large as O(N^2) since starting from each index there can be N-i potential words and there are N potential starting indices.
   • But we only store the indices, not the actual substrings, which are O(1) space each, so the more accurate complexity for the answer list is O(N^2).

The total space complexity is O(26 * W * L + N^2), which is O(W * L + N^2) because the 26 is a constant factor that doesn't change with the input size and can be omitted in big O notation.

Learn more about how to find time and space complexity quickly using problem constraints.