1408. String Matching in an Array - Detailed Explanation

Problem Statement

Description:
Given an array of strings words, return all strings in words that are a substring of another word in any order. A string is considered a substring of another if it can be found continuously in that other string.

Examples:

Example 1:
- Input: words = ["mass", "as", "hero", "superhero"]
- Output: ["as", "hero"]
- Explanation:
  - The word "as" is a substring of "mass".
  - The word "hero" is a substring of "superhero".
  - The words "mass" and "superhero" are not substrings of any other words in the list.
Example 2:
- Input: words = ["leetcode", "et", "code"]
- Output: ["et", "code"]
- Explanation:
  - "et" is a substring of "leetcode".
  - "code" is a substring of "leetcode".
  - "leetcode" is not a substring of any other word.
Example 3:
- Input: words = ["blue", "green", "bu"]
- Output: []
- Explanation:
  None of the words is a substring of another word.

Constraints:

1 ≤ words.length ≤ 100
1 ≤ words[i].length ≤ 30
All the strings of words are unique.

Hints Before the Solution

Brute Force Check:
Consider iterating over each word and checking if it appears as a substring in any other word. Since the constraints are small, a double loop with built-in substring checks (using methods like Python’s in or Java’s indexOf) is efficient enough.
Avoid Self-Comparison:
When checking if a word is a substring of another, make sure not to compare the word with itself.

Approaches

Approach 1: Brute Force

Idea:

For each word in the list, check every other word to see if the current word is a substring of that other word.
If it is, add the current word to the result list.
Since each word’s length is short and the array size is small, this solution is acceptable.

Steps:

Iterate over every word w in words.
For each w, iterate over every other word w2 in words.
Check if w is a substring of w2 (and ensure w is not the same as w2).
If yes, record w in the result.
Return the result list.

Time Complexity:

O(n² * m) where n is the number of words and m is the average length of the words.

Approach 2: Optimized Considerations

While the brute force approach is simple and effective given the constraints, you can consider a slight optimization by sorting the list based on word lengths. The idea is that shorter words are more likely to be substrings of longer words, and you can limit comparisons. However, note that sorting doesn’t change the worst-case complexity but can reduce unnecessary comparisons in practice.

Code Implementations

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Complexity Analysis

Time Complexity:
O(n² * m) where:
- n is the number of words.
- m is the average length of each word (due to substring search).
Space Complexity:
O(n) for the result list, which in the worst case could store almost every word.

Step-by-Step Walkthrough with Visual Example

Consider the input words = ["mass", "as", "hero", "superhero"]:

Iteration for "mass":
- Compare with "as": Check if "mass" is a substring of "as" → False.
- Compare with "hero": Check if "mass" is a substring of "hero" → False.
- Compare with "superhero": Check if "mass" is a substring of "superhero" → False.
- "mass" is not added to the result.
Iteration for "as":
- Compare with "mass": Check if "as" is a substring of "mass" → True.
- Once a match is found, add "as" to the result and break out of the inner loop.
Iteration for "hero":
- Compare with "mass": Check if "hero" is a substring of "mass" → False.
- Compare with "as": Check if "hero" is a substring of "as" → False.
- Compare with "superhero": Check if "hero" is a substring of "superhero" → True.
- Add "hero" to the result.
Iteration for "superhero":
- Check against all others; none contain "superhero" as a substring.
- "superhero" is not added to the result.

Final Result: ["as", "hero"]

Common Mistakes

Self-Comparison:
Forgetting to ensure that a word is not compared with itself can lead to false positives.
Inefficient Searches:
Not taking advantage of built-in substring methods (like Python’s in or Java’s contains) may lead to overly complex code.
Duplicate Entries:
Although the problem guarantees unique words, accidentally adding a word more than once when it is a substring of multiple words is a common mistake. Using a break after finding the first match helps avoid this.

Edge Cases

Single Element Array:
With only one word, no word can be a substring of another, so the output should be an empty list.
No Matching Substrings:
When none of the words is a substring of another (e.g., ["blue", "green", "bu"]), the output should be an empty list.

Alternative Variation:
Return words that are not substrings of any other words. This would involve collecting words that do not meet the substring condition.
Related Problems for Further Practice:
- Longest Common Prefix
- Substring Search Problems
- Find the Longest Word in Dictionary Through Deleting
- Implement strStr() (finding a substring within a string)