We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Index Pairs of a String

Number: 1075

Difficulty: Easy

Paid? Yes

Companies: Amazon

Problem Description

Given a string text and an array of strings words, return an array of all index pairs [i, j] such that the substring text[i...j] is one of the words in words. The answer should be returned in sorted order where pairs are sorted by the first index and in case of a tie, by the second index.

Key Insights

  • The input size is small enough (text length up to 100, words up to 20) to allow a brute-force approach.
  • For each word in words, iterate over every possible starting index in text and check if a substring of the matching length equals the word.
  • Alternatively, building a trie from the words could be used for more efficient multi-string matching in larger inputs.
  • Overlapping matches are allowed, so ensure every possible starting position is checked.
  • Sorting the result at the end guarantees the required order.

Space and Time Complexity

Time Complexity: O(n * m * k) where n is the length of text, m is the number of words, and k is the average length of a word. Space Complexity: O(1) (ignoring the space for the output), as only a result list is maintained.

Solution

We solve the problem by iterating through each word in words and, for each word, scanning through the text to see if the substring starting at that index matches the word. If it does, record the starting and ending indices as a pair. After processing all words, sort the list of index pairs to meet the output requirements. This straightforward approach leverages simple substring comparisons.

Code Solutions

# Python solution for "Index Pairs of a String"

def indexPairs(text, words):
    # Initialize a list to store the result
    result = []
    # Iterate over each word in the list
    for word in words:
        word_length = len(word)
        # Check for every possible starting index in text
        for i in range(len(text) - word_length + 1):
            # If the substring of length equal to the word matches
            if text[i:i + word_length] == word:
                # Append the pair [i, i+word_length-1] to the result
                result.append([i, i + word_length - 1])
    # Sort the result list as per requirements
    result.sort()
    return result

# Example usage:
print(indexPairs("thestoryofleetcodeandme", ["story", "fleet", "leetcode"]))
← Back to All Questions