Problem Description

You are given a string text and an array of strings words. Your task is to find all the substrings in text that match any word in the words array.

For each matching substring found, you need to return its starting and ending indices as a pair [i, j], where:

• i is the starting index of the substring
• j is the ending index of the substring
• The substring text[i...j] (inclusive) exists in the words array

The output should be an array containing all such index pairs, sorted in a specific order:

1. First, sort by the starting index i (ascending)
2. If two pairs have the same starting index, sort by the ending index j (ascending)

For example, if text = "ababa" and words = ["aba", "ab"]:

• The substring "ab" appears at indices [0, 1] and [2, 3]
• The substring "aba" appears at indices [0, 2] and [2, 4]
• The result would be [[0, 1], [0, 2], [2, 3], [2, 4]]

The solution uses a brute force approach that:

1. Converts the words list to a set for O(1) lookup time
2. Iterates through all possible substrings of text using nested loops
3. Checks if each substring exists in the words set
4. Returns all matching index pairs in the required sorted order

Intuition

The key insight is that we need to examine every possible substring of the given text to check if it matches any word in our word list. This naturally leads us to think about generating all substrings systematically.

To generate all possible substrings, we can use two pointers: one for the starting position and one for the ending position. For each starting position i, we try all valid ending positions j where j >= i. This gives us the substring text[i:j+1].

The brute force approach becomes clear when we realize that:

1. We must check every possible substring (there's no way to skip substrings without potentially missing matches)
2. For each substring, we need to verify if it exists in the words array

To optimize the lookup operation, we convert the words list into a set. This transformation is crucial because:

• Checking membership in a list takes O(m) time where m is the number of words
• Checking membership in a set takes O(1) average time
• Since we're checking many substrings, this optimization significantly improves performance

The nested loop structure emerges naturally:

• Outer loop: iterate through all possible starting positions (0 to n-1)
• Inner loop: for each starting position, iterate through all possible ending positions (from the starting position to n-1)
• For each [i, j] pair, extract text[i:j+1] and check if it's in our words set

The beauty of this approach is that the nested loops inherently generate the pairs in the required sorted order - first by starting index, then by ending index - eliminating the need for additional sorting.

Learn more about Trie and Sorting patterns.

Solution Approach

The implementation follows a straightforward brute-force strategy with an optimization for fast lookups:

Step 1: Convert words list to a set

words = set(words)

This conversion is the first optimization. By converting the list to a set, we reduce the time complexity of checking if a substring exists in words from O(m) to O(1) on average, where m is the number of words.

Step 2: Get the length of the text

n = len(text)

We store the length to avoid recalculating it in our loops.

Step 3: Generate all substrings and check membership

return [
    [i, j] for i in range(n) for j in range(i, n) if text[i : j + 1] in words
]

This list comprehension implements the core logic:

• Outer loop for i in range(n): Iterates through all possible starting positions from 0 to n-1
• Inner loop for j in range(i, n): For each starting position i, iterates through all possible ending positions from i to n-1
  • Starting from i ensures we don't generate empty substrings
  • Going up to n-1 ensures we check all possible substring lengths
• Substring extraction text[i : j + 1]: Creates the substring from index i to j (inclusive)
  • Note: We use j + 1 because Python's slice notation [i:j+1] includes i but excludes j+1
• Membership check if text[i : j + 1] in words: Checks if the extracted substring exists in our words set
• Result collection [i, j]: If the substring is found, we add the pair [i, j] to our result

The nested loops naturally produce pairs in sorted order:

• Pairs are first ordered by i (outer loop runs from 0 to n-1)
• For the same i, pairs are ordered by j (inner loop runs from i to n-1)

Time Complexity: O(n² × k) where n is the length of text and k is the average length of substrings being checked Space Complexity: O(m) for the set storage where m is the number of words, plus the space for the output array

Example Walkthrough

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

Given:

• text = "abcab"
• words = ["ab", "bc", "ca"]

Step 1: Convert words to a set

words_set = {"ab", "bc", "ca"}

Step 2: Generate all substrings using nested loops

Let's trace through the nested loops systematically:

When i = 0 (starting at 'a'):

• j = 0: substring = text[0:1] = "a" → not in words_set
• j = 1: substring = text[0:2] = "ab" → found in words_set, add [0, 1]
• j = 2: substring = text[0:3] = "abc" → not in words_set
• j = 3: substring = text[0:4] = "abca" → not in words_set
• j = 4: substring = text[0:5] = "abcab" → not in words_set

When i = 1 (starting at 'b'):

• j = 1: substring = text[1:2] = "b" → not in words_set
• j = 2: substring = text[1:3] = "bc" → found in words_set, add [1, 2]
• j = 3: substring = text[1:4] = "bca" → not in words_set
• j = 4: substring = text[1:5] = "bcab" → not in words_set

When i = 2 (starting at 'c'):

• j = 2: substring = text[2:3] = "c" → not in words_set
• j = 3: substring = text[2:4] = "ca" → found in words_set, add [2, 3]
• j = 4: substring = text[2:5] = "cab" → not in words_set

When i = 3 (starting at 'a'):

• j = 3: substring = text[3:4] = "a" → not in words_set
• j = 4: substring = text[3:5] = "ab" → found in words_set, add [3, 4]

When i = 4 (starting at 'b'):

• j = 4: substring = text[4:5] = "b" → not in words_set

Final Result: [[0, 1], [1, 2], [2, 3], [3, 4]]

Notice how the pairs are naturally sorted by starting index first (0, 1, 2, 3), and if there were multiple matches starting at the same index, they would be sorted by ending index due to the inner loop's progression.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n² × m)

The algorithm uses nested loops to iterate through all possible substrings of the text:

• The outer loop runs n times (where n is the length of text)
• The inner loop runs up to n times for each iteration of the outer loop
• For each pair (i, j), we extract substring text[i:j+1] which takes O(j-i+1) time in the worst case, up to O(n)
• Checking membership in the set words takes O(m) time where m is the average length of words in the set (for string hashing and comparison)

Total: O(n²) iterations × O(n) for substring extraction × O(m) for set lookup = O(n³ × m)

However, since Python optimizes string slicing and hashing, and considering that m (average word length) is typically much smaller than n, the practical complexity is closer to O(n² × m).

Space Complexity: O(k × m + n²)

• O(k × m) for storing the set of words, where k is the number of words and m is the average word length
• The output list can contain up to O(n²) pairs in the worst case (when every possible substring is a match)
• Additional O(n) space for substring creation during iteration

Total space complexity: O(k × m + n²)

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

Common Pitfalls

1. Forgetting to Handle Empty Strings in Words Array

One common pitfall is not considering that the words array might contain empty strings. If an empty string exists in words, the algorithm would generate index pairs like [0, -1], [1, 0], etc., which are invalid since the ending index would be less than the starting index.

Problem Example:

text = "abc"
words = ["", "ab"]  # Empty string in words
# Would attempt to check text[i:i] which is empty string

Solution: Filter out empty strings when converting to a set:

words_set = set(word for word in words if word)

2. Incorrect Index Range in Substring Extraction

A frequent mistake is using text[i:j] instead of text[i:j+1] when extracting substrings. This off-by-one error occurs because Python's slice notation is exclusive of the end index, but the problem expects inclusive indices.

Problem Example:

# Incorrect:
substring = text[start_idx:end_idx]  # Missing the character at end_idx

# If text = "abc" and we want substring from index 0 to 2:
# text[0:2] gives "ab" instead of "abc"

Solution: Always use j+1 in the slice operation:

substring = text[start_idx:end_idx + 1]  # Correct: includes character at end_idx

3. Performance Degradation with Large Words Array

While converting to a set helps with lookup time, if the words array contains very long strings, the set creation and substring comparison can become expensive due to string hashing overhead.

Problem Example:

# If words contains many long strings:
words = ["a" * 1000, "b" * 1000, ...]  # Very long strings
# Each substring comparison requires hashing potentially long strings

Solution: Pre-compute the maximum and minimum word lengths to avoid checking substrings that can't possibly match:

words_set = set(words)
if not words_set:
    return []

min_word_len = min(len(word) for word in words_set)
max_word_len = max(len(word) for word in words_set)

result = []
for start_idx in range(len(text)):
    # Only check substrings within valid length range
    for end_idx in range(start_idx + min_word_len - 1, 
                         min(start_idx + max_word_len, len(text))):
        substring = text[start_idx:end_idx + 1]
        if substring in words_set:
            result.append([start_idx, end_idx])

4. Not Handling Duplicate Words in Input

While converting to a set naturally handles duplicates, developers might implement alternative solutions that don't account for duplicate words, leading to duplicate results or incorrect counting.

Problem Example:

words = ["ab", "ab", "abc"]  # "ab" appears twice
# Some implementations might process "ab" twice

Solution: The set conversion automatically handles this, but if using other approaches, ensure duplicates are removed:

words_set = set(words)  # Automatically removes duplicates