String Matching in an Array - Solution & Explanation

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.