String Matching in an Array - Solution & Explanation
Problem Statement
Given an array of string words, return all strings in words that is a substring of another word. You can return the answer in any order.
A substring is a contiguous sequence of characters within a string
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 <= 1001 <= words[i].length <= 30words[i]contains only lowercase English letters.- All the strings of
wordsare unique.
Approach Overview
Problem Overview: You are given an array of strings. The task is to return all words that appear as a substring of another word in the same array. For every word, you check whether it exists inside a different word using standard substring or contains operations.
Approach 1: Brute Force Comparison (O(n^2 * m) time, O(1) extra space)
The direct solution compares every word with every other word. Iterate through the array using two nested loops. For each pair (i, j), check if words[j] contains words[i] using built‑in string search such as find(), contains(), or indexOf(). If the substring exists and i != j, add the smaller word to the result. The complexity comes from checking all pairs (n^2) and performing substring search that may scan up to the length of the longer string (m). This approach is simple and works well for the small input sizes typical of array and string interview problems.
Approach 2: Efficient Set-based Comparison (O(n^2 * m) time, O(n) space)
A cleaner implementation uses a HashSet to store all words for quick membership management. Insert all words into a set, then iterate through the list. Temporarily remove the current word so it is not matched with itself. Compare it against the remaining words and check if any string contains it as a substring. The set simplifies duplicate handling and prevents accidental self-matching. While the worst‑case complexity remains O(n^2 * m), the constant factors are slightly lower because each word is handled only once and lookups are O(1). This approach still relies on standard string matching operations provided by the language runtime.
Recommended for interviews: Start with the brute force pairwise comparison. It clearly demonstrates understanding of substring checks and pair iteration. Then mention the set-based refinement to improve code clarity and avoid self-comparisons. Interviewers mainly evaluate whether you recognize that the problem reduces to repeated substring search across the array.
Approach 1: Brute Force Comparison
This approach is straightforward: for each word in the list, check if it is a substring of any other word. We iterate over each pair of words in the array and use string operations to check for substrings.
The solution defines a helper function isSubstring to check if a word is a substring of another using strstr. The main logic iterates over each word, comparing it with every other word and stores indices of valid substrings.
Complexity
Time Complexity: O(n^2 * m)
Space Complexity: O(n)
Approach 2: Efficient Set-based Comparison
This approach creates all possible substrings of each word and stores them in a set, which is then used to quickly check for substring membership against other words.
This efficient set-based comparison uses direct substring checking. The main difference from the brute force approach is potential pre-processing for sets (not shown due to C limitations), leading to conceptually similar efficiency given current size constraints.
Complexity
Time Complexity: O(n^2 * m)
Space Complexity: O(n)
Approach 3: Brute Force Enumeration
We directly enumerate all strings words[i], and check whether it is a substring of other strings. If it is, we add it to the answer.
The time complexity is O(n^3), and the space complexity is O(n). Where n is the length of the string array.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Comparison | Time Complexity: O(n^2 * m) |
| Efficient Set-based Comparison | Time Complexity: O(n^2 * m) |
| Brute Force Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Comparison | O(n^2 * m) | O(1) | Simple implementation and small input sizes |
| Efficient Set-based Comparison | O(n^2 * m) | O(n) | Cleaner logic, avoids self-comparison and handles duplicates easily |
Video Solution
String Matching in an Array - Leetcode 1408 - Python • NeetCodeIO • 14,671 views views
Watch 9 more video solutions →Frequently Asked Questions
Is String Matching in an Array easy or hard?
String Matching in an Array Python/Java solution
How to solve String Matching in an Array in O(n)?
What is the best approach for String Matching in an Array?
Is String Matching in an Array asked at Google/Amazon/Meta?
What data structure is used in String Matching in an Array?
What is the time complexity of String Matching in an Array?
Ready to solve this problem?
Practice String Matching in an Array with our built-in code editor and test cases.
Practice on FleetCode