#1408

Easy

LeetCode Problem Workspace

String Matching in an Array

Identify all strings in an array that appear as substrings of other strings, focusing on array and string matching patterns.

array string string matching

Problem Statement

Given an array of unique lowercase strings, return all strings that are substrings of another string in the array. The output can be in any order, and you must account for every pair of words to check containment accurately.

For example, if the input array is ["mass","as","hero","superhero"], the strings "as" and "hero" are substrings of "mass" and "superhero" respectively, so the output should be ["as","hero"]. Similar checks must be applied for any array of strings while respecting uniqueness and length constraints.

Examples

Example 1

Input: words = ["mass","as","hero","superhero"]

Output: ["as","hero"]

"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"]

"et", "code" are substring of "leetcode".

Example 3

Input: words = ["blue","green","bu"]

Output: []

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.

Solution Approach

Brute Force Pairwise Check

Iterate through all pairs of strings and check if one string is a substring of the other using built-in functions. Add matches to a result set to avoid duplicates. This approach directly applies the array plus string pattern and clearly demonstrates the substring containment logic.

Optimized Search with Sorting

Sort the array by string length descending, then for each string check if any longer string contains it as a substring. This reduces unnecessary comparisons and highlights the common failure mode of comparing shorter strings against all others without optimization.

KMP Algorithm for Substring Detection

For larger datasets or stricter performance needs, use the Knuth-Morris-Pratt algorithm to check substring matches efficiently. Preprocess each string pattern to reduce repeated scanning, maintaining the array plus string problem pattern while improving time complexity.

Complexity Analysis

Metric	Value
Time	O(m^2 \times n)
Space	O(m^2 \times n)

Time complexity is O(m^2 \times n) because each of the m strings is compared with every other string, and each comparison may scan up to n characters. Space complexity is O(m^2 \times n) when storing substring results, especially if using sets to avoid duplicates.

What Interviewers Usually Probe

Check if candidates attempt naive pairwise comparisons or optimize using sorting by length.
Observe if candidates consider substring edge cases like identical or nested substrings.
Listen for discussion on using string search algorithms such as KMP to improve efficiency.

Common Pitfalls or Variants

Common pitfalls

Failing to account for all pairs, missing substrings contained in multiple words.
Returning duplicates if using lists instead of sets for results.
Ignoring constraints and attempting unnecessary optimizations for small arrays.

Follow-up variants

Return substrings that appear in at least k other strings instead of just one.
Count the total number of substring occurrences across all words instead of returning the words.
Find substrings that are both prefixes and suffixes of other words, combining array plus string logic.

FAQ

What is the main pattern in the String Matching in an Array problem?

The main pattern is array plus string: you must check which strings in the array are substrings of other strings.

Can I return the substrings in any order?

Yes, the output can be in any order as long as it contains all strings that are substrings of another word.

Is using built-in substring functions acceptable?

Yes, built-in functions are fine for brute force checks, though KMP can improve efficiency for larger arrays.

What is the time complexity of the brute force solution?

It is O(m^2 \times n), where m is the number of strings and n is the maximum length of a string.

How does GhostInterview assist with this problem?

It guides you to apply pairwise substring checks, consider optimizations, and correctly manage duplicates in results.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        ans = []
        for i, s in enumerate(words):
            if any(i != j and s in t for j, t in enumerate(words)):
                ans.append(s)
        return ans

Continue Practicing

#1023 camelcase matching #2185 counting words with a given prefix #2301 match substring after replacement