Jobs

Interviews

Discussions

Index Pairs of a String

Easy

Asked by:

8 views

Topics:

StringsArrays

Given a string text and an array of strings words, return an array of all the index pairs [i, j] so that the substring text[i...j] is in the array words. You should sort the [i, j] pairs in lexicographical order (i.e., sort the first index in ascending order, and if two pairs have the same first index, sort them by the second index in ascending order).

Example 1:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

Example 2:

Input: text = "ababa", words = ["aba","ab"]

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

Explanation:

Notice that the output is sorted lexicographically.

Constraints:

1 <= text.length <= 100
1 <= words.length <= 100
1 <= words[i].length <= 30
text and words[i] consist of lowercase English letters.
All the strings of words are unique.

Try coding it in LeetCode

Index Pairs of a String

Easy

Asked by:

8 views

Topics:

StringsArrays

Example 1:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

Example 2:

Input: text = "ababa", words = ["aba","ab"]

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

Explanation:

Notice that the output is sorted lexicographically.

Constraints:

1 <= text.length <= 100
1 <= words.length <= 100
1 <= words[i].length <= 30
text and words[i] consist of lowercase English letters.
All the strings of words are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the words in the `words` array contain overlapping occurrences within the `text` string?
How should the index pairs be ordered in the output array?
What should be returned if none of the words in the `words` array are found in the `text` string?
Are the words in the `words` array guaranteed to be unique, or could there be duplicates?
Are the `text` and `words` arrays case-sensitive, or should I perform a case-insensitive search?

Brute Force Solution

Approach

The brute force method to find pairs of starting and ending positions for specific words within a larger piece of text involves looking at every possible place a word could start and end. We painstakingly check each potential word against our list of target words. If a match is found, we record its starting and ending position.

Here's how the algorithm would work step-by-step:

Take the first possible position in the text as a potential starting point for a target word.
Check every target word to see if it begins at that position.
If a target word starts at that position, determine where it ends.
Record the starting and ending positions of the match.
Move to the next possible starting position in the text.
Repeat steps 2-4 for this new starting position.
Continue until you have checked every possible starting position in the text.
Return the collection of all the matching starting and ending position pairs you have found.

Code Implementation

def index_pairs_of_a_string_brute_force(text, words):
    index_pairs = []
    text_length = len(text)

    for starting_position in range(text_length):
        # Iterate through the target words to check for matches.

        for target_word in words:
            word_length = len(target_word)
            # Check if the target word fits within the remaining text

            if starting_position + word_length <= text_length:
                substring = text[starting_position:starting_position + word_length]

                if substring == target_word:
                    ending_position = starting_position + word_length - 1

                    index_pairs.append([starting_position, ending_position])

    return index_pairs

Big(O) Analysis

Time Complexity

O(n*m*k) – Let n be the length of the text string, m be the number of words in the searchWords array, and k be the maximum length of a word in the searchWords array. The algorithm iterates through each possible starting position in the text string (n iterations). For each starting position, it iterates through each word in the searchWords array (m iterations). For each word, it performs a string comparison, which in the worst case, could be proportional to the length of the word (k iterations). Thus, the overall time complexity is O(n*m*k).

Space Complexity

O(K*L) – The provided algorithm stores matching starting and ending position pairs in a collection. In the worst-case scenario, every substring of the text might match a word in the list of target words, where K is the length of the input text and L is the total combined length of all the target words in the target word list. Therefore, the number of pairs stored in the collection would be proportional to K*L, where each pair comprises two integers. Thus the algorithm uses auxiliary space to store the index pairs.

Optimal Solution

Approach

The most efficient way to solve this problem is to search for each target word within the large string using a technique that avoids repeatedly checking the same locations. By pre-processing the list of target words, we can quickly locate all occurrences within the main string.

Here's how the algorithm would work step-by-step:

First, organize the list of target words to help with quick lookups. Think of creating a table where each target word is easily accessible.
Then, go through the large string character by character.
At each character, check if any of the target words start at that point.
If a target word is found starting at the current character, record the starting and ending positions of that word.
Continue scanning the large string, remembering to avoid re-checking areas where a target word has already been found.
Finally, arrange all the recorded start and end positions in increasing order. This provides the complete list of matching index pairs.

Code Implementation

def find_index_pairs(main_string, target_words):
    index_pairs = []
    target_word_set = set(target_words)

    # Converting to set enables faster lookup
    for i in range(len(main_string)):

        for target_word in target_word_set:
            if main_string[i:].startswith(target_word):
                # Record the starting and ending indices
                index_pairs.append([i, i + len(target_word) - 1])

    # Sort index pairs to meet output requirements
    index_pairs.sort()

    return index_pairs

Big(O) Analysis

Time Complexity

O(n*m*k) – Let n be the length of the large string, m be the number of target words, and k be the average length of the target words. We iterate through the large string of length n. At each position, we iterate through the m target words to check if any of them start at that position. The check itself takes O(k) time, where k is the average length of the target words, as we compare the target word with the substring of the large string. Therefore, the overall time complexity is O(n*m*k).

Space Complexity

O(T + P) – The space complexity is determined by the auxiliary space used to store the target words in a data structure for quick lookup, which we'll assume takes O(T) space where T is the total number of characters in all target words. Additionally, we store the starting and ending positions of found words which, in the worst case, could include every character position in the large string P, creating a list of index pairs. Thus, the space needed to store these index pairs could grow linearly with the length of the large string P in the worst-case scenario where every character is the start of a match. Hence, the overall space complexity is O(T + P), where T represents the space needed to store the target words and P represents the potential space for storing index pairs.

Edge Cases

Case	How to Handle
Empty text string	Return an empty list of index pairs as there are no substrings.
Empty words array	Return an empty list of index pairs as there are no words to find.
Text string is null or undefined	Throw an IllegalArgumentException or return an empty list based on requirements.
Words array is null or undefined	Throw an IllegalArgumentException or return an empty list based on requirements.
Words array contains an empty string	Skip the empty string and proceed with the rest of the words, or throw an exception depending on specification.
Words array contains duplicate words	The algorithm should correctly identify all occurrences of each duplicated word in the text.
Word is a substring of another word in the words array	The algorithm should identify all occurrences of both substrings without interference.
Very long text string and very large words array; potential for performance issues	Consider optimizing the search algorithm (e.g., using Aho-Corasick or other efficient string matching algorithms) if performance degrades significantly.

Empty text string

How to Handle:

Return an empty list of index pairs as there are no substrings.

Empty words array

How to Handle:

Return an empty list of index pairs as there are no words to find.

Text string is null or undefined

How to Handle:

Throw an IllegalArgumentException or return an empty list based on requirements.

Words array is null or undefined

How to Handle:

Throw an IllegalArgumentException or return an empty list based on requirements.

Words array contains an empty string

How to Handle:

Skip the empty string and proceed with the rest of the words, or throw an exception depending on specification.

Words array contains duplicate words

How to Handle:

The algorithm should correctly identify all occurrences of each duplicated word in the text.

Word is a substring of another word in the words array

How to Handle:

The algorithm should identify all occurrences of both substrings without interference.

Very long text string and very large words array; potential for performance issues

How to Handle:

Consider optimizing the search algorithm (e.g., using Aho-Corasick or other efficient string matching algorithms) if performance degrades significantly.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the words in the `words` array contain overlapping occurrences within the `text` string?
How should the index pairs be ordered in the output array?
What should be returned if none of the words in the `words` array are found in the `text` string?
Are the words in the `words` array guaranteed to be unique, or could there be duplicates?
Are the `text` and `words` arrays case-sensitive, or should I perform a case-insensitive search?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first possible position in the text as a potential starting point for a target word.
Check every target word to see if it begins at that position.
If a target word starts at that position, determine where it ends.
Record the starting and ending positions of the match.
Move to the next possible starting position in the text.
Repeat steps 2-4 for this new starting position.
Continue until you have checked every possible starting position in the text.
Return the collection of all the matching starting and ending position pairs you have found.

Code Implementation

def index_pairs_of_a_string_brute_force(text, words):
    index_pairs = []
    text_length = len(text)

    for starting_position in range(text_length):
        # Iterate through the target words to check for matches.

        for target_word in words:
            word_length = len(target_word)
            # Check if the target word fits within the remaining text

            if starting_position + word_length <= text_length:
                substring = text[starting_position:starting_position + word_length]

                if substring == target_word:
                    ending_position = starting_position + word_length - 1

                    index_pairs.append([starting_position, ending_position])

    return index_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, organize the list of target words to help with quick lookups. Think of creating a table where each target word is easily accessible.
Then, go through the large string character by character.
At each character, check if any of the target words start at that point.
If a target word is found starting at the current character, record the starting and ending positions of that word.
Continue scanning the large string, remembering to avoid re-checking areas where a target word has already been found.
Finally, arrange all the recorded start and end positions in increasing order. This provides the complete list of matching index pairs.

Code Implementation

def find_index_pairs(main_string, target_words):
    index_pairs = []
    target_word_set = set(target_words)

    # Converting to set enables faster lookup
    for i in range(len(main_string)):

        for target_word in target_word_set:
            if main_string[i:].startswith(target_word):
                # Record the starting and ending indices
                index_pairs.append([i, i + len(target_word) - 1])

    # Sort index pairs to meet output requirements
    index_pairs.sort()

    return index_pairs

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty text string	Return an empty list of index pairs as there are no substrings.
Empty words array	Return an empty list of index pairs as there are no words to find.
Text string is null or undefined	Throw an IllegalArgumentException or return an empty list based on requirements.
Words array is null or undefined	Throw an IllegalArgumentException or return an empty list based on requirements.
Words array contains an empty string	Skip the empty string and proceed with the rest of the words, or throw an exception depending on specification.
Words array contains duplicate words	The algorithm should correctly identify all occurrences of each duplicated word in the text.
Word is a substring of another word in the words array	The algorithm should identify all occurrences of both substrings without interference.
Very long text string and very large words array; potential for performance issues	Consider optimizing the search algorithm (e.g., using Aho-Corasick or other efficient string matching algorithms) if performance degrades significantly.

Empty text string

How to Handle:

Return an empty list of index pairs as there are no substrings.

Empty words array

How to Handle:

Return an empty list of index pairs as there are no words to find.

Text string is null or undefined

How to Handle:

Throw an IllegalArgumentException or return an empty list based on requirements.

Words array is null or undefined

How to Handle:

Throw an IllegalArgumentException or return an empty list based on requirements.

Words array contains an empty string

How to Handle:

Skip the empty string and proceed with the rest of the words, or throw an exception depending on specification.

Words array contains duplicate words

How to Handle:

The algorithm should correctly identify all occurrences of each duplicated word in the text.

Word is a substring of another word in the words array

How to Handle:

The algorithm should identify all occurrences of both substrings without interference.

Very long text string and very large words array; potential for performance issues

How to Handle:

Consider optimizing the search algorithm (e.g., using Aho-Corasick or other efficient string matching algorithms) if performance degrades significantly.