How to Solve String Matching in an Array

This problem requires detecting which words in an array are substrings of other words. A straightforward approach iterates over all pairs and checks containment, while more advanced methods could apply KMP for substring detection. The key challenge is efficiently handling multiple string comparisons while ensuring no duplicates in the output.

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

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.

How GhostInterview Helps

• Highlights the correct brute force implementation for detecting substring relationships in arrays.
• Suggests optimizations like sorting by length and using sets to avoid duplicates.
• Provides guidance on applying KMP for efficient substring checking while maintaining correct output.

Topic Pages

• Array
• String
• String Matching

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.