Jobs

Interviews

Discussions

String Matching in an Array

Easy

Asked by:

More companies

56 views

Topics:

ArraysStringsTwo Pointers

Given an array of string words, return all strings in words that are a substring of another word. You can return the answer in any order.

Example 1:

Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is substring of "mass" and "hero" is substring of "superhero".
["hero","as"] is also a valid answer.

Example 2:

Input: words = ["leetcode","et","code"]
Output: ["et","code"]
Explanation: "et", "code" are substring of "leetcode".

Example 3:

Input: words = ["blue","green","bu"]
Output: []
Explanation: No string of words is substring of another string.

Constraints:

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

Try coding it in LeetCode

String Matching in an Array

Easy

Asked by:

56 views

Topics:

ArraysStringsTwo Pointers

Given an array of string words, return all strings in words that are a substring of another word. You can return the answer in any order.

Example 1:

Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is substring of "mass" and "hero" is substring of "superhero".
["hero","as"] is also a valid answer.

Example 2:

Input: words = ["leetcode","et","code"]
Output: ["et","code"]
Explanation: "et", "code" are substring of "leetcode".

Example 3:

Input: words = ["blue","green","bu"]
Output: []
Explanation: No string of words is substring of another string.

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 30
words[i] contains only 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 input strings contain special characters or only alphanumeric characters?
Is the matching case-sensitive, or should I perform case-insensitive comparisons?
If a string is a substring of multiple other strings, should it be included multiple times in the output, or only once?
What should I return if the input array is empty or null?
What is the maximum length of the individual strings in the array?

Brute Force Solution

Approach

The brute force method checks every single word in the list to see if it's contained in every other word. It's like comparing each word against all the others, one by one, to find matches.

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

Pick the first word from the list.
Take the second word and see if the first word is part of it.
Then, take the third word and see if the first word is part of it, and so on.
Repeat this process for all the remaining words in the list to check if the first word is a part of any of them.
Now, move to the second word in the list.
Compare the second word to all the other words (except itself) in the list, checking if it is a part of any of them.
Keep doing this for each word in the list, comparing it to all the other words until you've checked all possible pairs.
Keep track of all the words that are found inside other words.
At the end, you'll have a list of all the words that are substrings of at least one other word in the original list.

Code Implementation

def string_matching_in_array(words):
    matching_words = []
    number_of_words = len(words)

    for i in range(number_of_words):
        for j in range(number_of_words):
            # Ensure we don't compare a word with itself.
            if i != j:
                # Check if word at index i is a substring of word at index j.
                if words[i] in words[j]:
                    # Only add if it's not already in the matching words list
                    if words[i] not in matching_words:
                        matching_words.append(words[i])

    return matching_words

Big(O) Analysis

Time Complexity

O(n² * k) – The algorithm iterates through each of the n words in the input array. For each word, it compares it against the other n-1 words. The `contains` operation, or a similar substring search, takes up to O(k) time, where k is the average length of the strings. Since we perform n * (n-1) comparisons, each costing up to O(k) time, the total time complexity is O(n * (n-1) * k). Simplifying, the time complexity becomes O(n² * k).

Space Complexity

O(N) – The provided solution uses a list (or set) to keep track of all words that are substrings of at least one other word. In the worst-case scenario, every word except one could be a substring of another word. Therefore, the space required to store these matching words could grow linearly with the number of words in the input array. Thus, the auxiliary space complexity is O(N), where N is the number of words in the input array.

Optimal Solution

Approach

The goal is to find strings within an array that are contained inside other strings. The most efficient approach avoids unnecessary comparisons by first ordering the strings and then checking if shorter strings are inside longer ones.

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

First, organize the strings by their length, from shortest to longest. This way, you only need to check if shorter strings exist within longer ones.
Then, for each string in the sorted list, check if it's part of any of the longer strings that come after it in the list.
If a shorter string is found within a longer string, remember it. These are the strings you need to find.
Finally, list out all the strings you remembered; these are the strings that are contained within others.

Code Implementation

def string_matching_in_array(words):
    words.sort(key=len)

    result = []
    for i in range(len(words)):
        # Iterate through the sorted list of words.

        for j in range(i + 1, len(words)):
            # Only check against longer strings to avoid redundant comparisons.

            if words[i] in words[j]:
                result.append(words[i])
                break
                # Avoid re-adding if found in multiple words

    return result

Big(O) Analysis

Time Complexity

O(n²) – Sorting the array of strings by length can be done in O(n log n) time, but this is dominated by the subsequent nested loops. The outer loop iterates through each of the n strings. The inner loop, in the worst case, iterates through the remaining strings to check for containment. Each containment check using string.contains() is O(m) where m is the length of the longer string which is bounded by the maximum length of a string within the input array. However, in the worst case scenario where strings are of similar lengths, it approaches O(1) and is less significant than the nested loops. The pair checking drives the cost, approximating n * (n-1)/2 operations. Therefore, the dominant factor is O(n²).

Space Complexity

O(N) – The algorithm sorts the input array of strings. While some sorting algorithms can be done in-place, a typical implementation often requires creating a new sorted array, taking O(N) space, where N is the number of strings. Additionally, the algorithm stores the matching substrings in a result list, which in the worst case, could store all the input strings resulting in O(N) space. Thus, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Input array is null or undefined	Throw an IllegalArgumentException or return an empty list to prevent NullPointerException.
Input array is empty	Return an empty list immediately as there are no strings to compare.
Input array contains only one string	Return an empty list since a string needs at least another to be a substring of it.
Input array contains empty strings	Handle empty strings carefully; an empty string is a substring of every string, so it should be added to the result only if other strings exist and if it is not itself one of the others substring.
Long strings causing performance issues	Consider using more efficient substring search algorithms like Knuth-Morris-Pratt (KMP) or Boyer-Moore for very long strings.
Array contains duplicate strings	The algorithm should still function correctly, identifying substring relationships even if the same string appears multiple times.
One string is equal to another string	Handle equality; a string is not considered a substring of itself in this case, so do not include it in the output.
Maximum array size exceeds memory limitations	Consider breaking the input into smaller chunks or using external storage/processing if the array is too large to fit in memory.

Input array is null or undefined

How to Handle:

Throw an IllegalArgumentException or return an empty list to prevent NullPointerException.

Input array is empty

How to Handle:

Return an empty list immediately as there are no strings to compare.

Input array contains only one string

How to Handle:

Return an empty list since a string needs at least another to be a substring of it.

Input array contains empty strings

How to Handle:

Handle empty strings carefully; an empty string is a substring of every string, so it should be added to the result only if other strings exist and if it is not itself one of the others substring.

Long strings causing performance issues

How to Handle:

Consider using more efficient substring search algorithms like Knuth-Morris-Pratt (KMP) or Boyer-Moore for very long strings.

Array contains duplicate strings

How to Handle:

The algorithm should still function correctly, identifying substring relationships even if the same string appears multiple times.

One string is equal to another string

How to Handle:

Handle equality; a string is not considered a substring of itself in this case, so do not include it in the output.

Maximum array size exceeds memory limitations

How to Handle:

Consider breaking the input into smaller chunks or using external storage/processing if the array is too large to fit in memory.

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 input strings contain special characters or only alphanumeric characters?
Is the matching case-sensitive, or should I perform case-insensitive comparisons?
If a string is a substring of multiple other strings, should it be included multiple times in the output, or only once?
What should I return if the input array is empty or null?
What is the maximum length of the individual strings in the array?

Brute Force Solution

Approach

The brute force method checks every single word in the list to see if it's contained in every other word. It's like comparing each word against all the others, one by one, to find matches.

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

Pick the first word from the list.
Take the second word and see if the first word is part of it.
Then, take the third word and see if the first word is part of it, and so on.
Repeat this process for all the remaining words in the list to check if the first word is a part of any of them.
Now, move to the second word in the list.
Compare the second word to all the other words (except itself) in the list, checking if it is a part of any of them.
Keep doing this for each word in the list, comparing it to all the other words until you've checked all possible pairs.
Keep track of all the words that are found inside other words.
At the end, you'll have a list of all the words that are substrings of at least one other word in the original list.

Code Implementation

def string_matching_in_array(words):
    matching_words = []
    number_of_words = len(words)

    for i in range(number_of_words):
        for j in range(number_of_words):
            # Ensure we don't compare a word with itself.
            if i != j:
                # Check if word at index i is a substring of word at index j.
                if words[i] in words[j]:
                    # Only add if it's not already in the matching words list
                    if words[i] not in matching_words:
                        matching_words.append(words[i])

    return matching_words

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, organize the strings by their length, from shortest to longest. This way, you only need to check if shorter strings exist within longer ones.
Then, for each string in the sorted list, check if it's part of any of the longer strings that come after it in the list.
If a shorter string is found within a longer string, remember it. These are the strings you need to find.
Finally, list out all the strings you remembered; these are the strings that are contained within others.

Code Implementation

def string_matching_in_array(words):
    words.sort(key=len)

    result = []
    for i in range(len(words)):
        # Iterate through the sorted list of words.

        for j in range(i + 1, len(words)):
            # Only check against longer strings to avoid redundant comparisons.

            if words[i] in words[j]:
                result.append(words[i])
                break
                # Avoid re-adding if found in multiple words

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input array is null or undefined	Throw an IllegalArgumentException or return an empty list to prevent NullPointerException.
Input array is empty	Return an empty list immediately as there are no strings to compare.
Input array contains only one string	Return an empty list since a string needs at least another to be a substring of it.
Input array contains empty strings	Handle empty strings carefully; an empty string is a substring of every string, so it should be added to the result only if other strings exist and if it is not itself one of the others substring.
Long strings causing performance issues	Consider using more efficient substring search algorithms like Knuth-Morris-Pratt (KMP) or Boyer-Moore for very long strings.
Array contains duplicate strings	The algorithm should still function correctly, identifying substring relationships even if the same string appears multiple times.
One string is equal to another string	Handle equality; a string is not considered a substring of itself in this case, so do not include it in the output.
Maximum array size exceeds memory limitations	Consider breaking the input into smaller chunks or using external storage/processing if the array is too large to fit in memory.

Input array is null or undefined

How to Handle:

Throw an IllegalArgumentException or return an empty list to prevent NullPointerException.

Input array is empty

How to Handle:

Return an empty list immediately as there are no strings to compare.

Input array contains only one string

How to Handle:

Return an empty list since a string needs at least another to be a substring of it.

Input array contains empty strings

How to Handle:

Handle empty strings carefully; an empty string is a substring of every string, so it should be added to the result only if other strings exist and if it is not itself one of the others substring.

Long strings causing performance issues

How to Handle:

Consider using more efficient substring search algorithms like Knuth-Morris-Pratt (KMP) or Boyer-Moore for very long strings.

Array contains duplicate strings

How to Handle:

The algorithm should still function correctly, identifying substring relationships even if the same string appears multiple times.

One string is equal to another string

How to Handle:

Handle equality; a string is not considered a substring of itself in this case, so do not include it in the output.

Maximum array size exceeds memory limitations

How to Handle:

Consider breaking the input into smaller chunks or using external storage/processing if the array is too large to fit in memory.