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.words are unique.In #1408 String Matching in an Array, the goal is to identify all words that appear as a substring of another word in the given array. A straightforward strategy is to compare every word with every other word and check whether one appears inside the other using built‑in substring checks such as contains().
The common approach is to iterate through each word and test it against the remaining words in the array. If the current word is found within another word, it should be added to the result set. To slightly optimize the process, you can sort words by length so shorter words are checked against longer ones only.
This method is efficient enough because the input size is relatively small. The main cost comes from pairwise comparisons and substring searches, giving a time complexity around O(n² × L), where n is the number of words and L is the average string length.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Pairwise comparison with substring check | O(n² × L) | O(1) extra (excluding output) |
Abdul Bari
Use these hints if you're stuck. Try solving on your own first.
Bruteforce to find if one string is substring of another or use KMP algorithm.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of substring search and string comparison problems are common in coding interviews at large tech companies. This problem tests basic string manipulation and understanding of time complexity.
Arrays and basic string operations are usually enough for this problem. While advanced structures like tries or algorithms like KMP can be used, they are unnecessary for the typical constraints of this problem.
The most common approach is to compare each word with all other words and check if it appears as a substring using built-in string search functions. Because the input size is small, this O(n² × L) solution is usually sufficient and easy to implement.
Yes, algorithms such as KMP or Rabin–Karp can be applied to detect substrings efficiently. However, for the typical input size in this problem, simple substring checks are easier to implement and sufficiently fast.