String Matching in an Array

Problem Description

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.

Key Insights

• The problem requires checking for substrings within a list of unique strings.
• Efficient substring checking can be achieved by comparing each word against others.
• The constraints allow for a straightforward approach due to the manageable input size.

Space and Time Complexity

Time Complexity: O(n^2 * m), where n is the number of words and m is the average length of the words. Space Complexity: O(k), where k is the number of substrings found that are stored in the result.

Solution

To solve this problem, we can use a straightforward approach involving nested loops. We will iterate through each word and check if it is a substring of any other word in the list. The key data structure here is a list to store the results. Since all strings are unique, we do not need to handle duplicates in our results.

1. Initialize an empty list to hold the result.
2. For each word in the list, iterate through the list again to check if the current word is a substring of any other word.
3. If it is found as a substring, add it to the result list.
4. Finally, return the result.

Code Solutions