Problem Description

The Leetcode problem String Matching in an Array asks you to process an array of strings, words. Your task is to find all strings in the array that are substrings of another string in the same array.

• Return all such strings in any order.
• Each string in words is unique.
• Do not reuse elements; a string should not be matched with itself.
• There can be more than one valid solution, and the order of the output does not matter.

Example:
Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is a substring of "mass" and "hero" is a substring of "superhero".

Thought Process

At first glance, the problem suggests checking every string against all others to see if it appears as a substring. This brute-force approach is straightforward but potentially inefficient for large arrays.

The key insight is that for each string, we only care if it exists as a substring in any of the other strings. Since the list of words is usually small (according to constraints), a double loop is acceptable, but we can optimize further by avoiding unnecessary checks (like comparing a word with itself).

The conceptual shift is to recognize that substring checks are fast for short strings and that the array size is manageable, so a simple nested loop is both readable and efficient.

Solution Approach

Let's break down the solution step by step:

1. Initialize an empty result list.
   We'll store all strings that are substrings of another.
2. Iterate through each word in the array.
   For each word, check if it is a substring of any other word.
3. For each word, loop through the array again.
   Skip the check if it's the same word (avoid self-comparison).
4. Use the substring check.
   In most languages, this is a simple if word in other_word or equivalent.
5. If a substring is found, add the word to the result list and break the inner loop.
   No need to check further for that word.
6. Return the result list.

This approach is simple, easy to implement, and efficient enough for the problem's constraints.

Example Walkthrough

Let's walk through the sample input:

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

1. Check "mass":
   • "as" in "mass"? Yes, but we're checking "mass" as a whole.
   • "mass" in "as"? No.
   • "mass" in "hero"? No.
   • "mass" in "superhero"? No.
   "mass" is not a substring of any other word.
2. Check "as":
   • "as" in "mass"? Yes. Add "as" to result.
   No need to check further for "as".
3. Check "hero":
   • "hero" in "mass"? No.
   • "hero" in "as"? No.
   • "hero" in "superhero"? Yes. Add "hero" to result.
   Stop checking further for "hero".
4. Check "superhero":
   • "superhero" in "mass"? No.
   • "superhero" in "as"? No.
   • "superhero" in "hero"? No.
   "superhero" is not a substring of any other word.

Final output: ["as", "hero"]

Time and Space Complexity

• Brute-force Approach:
  For each word, we check all other words. If there are n words and the average word length is m, the time complexity is O(n^2 * m), since substring checking is up to O(m) for each pair.
• Optimized Approach:
  Since we skip checking a word with itself and break early when a substring is found, the average case is faster, but the worst case remains O(n^2 * m).
• Space Complexity:
  We only use extra space for the result list, which can be up to O(n) in the worst case.

Summary

The "String Matching in an Array" problem is elegantly solved with a straightforward double loop, checking each string as a potential substring of every other. The constraints allow this approach, and the solution is both readable and efficient for the expected input sizes. The key insight is to avoid unnecessary checks and to break early when a match is found, making the code simple yet effective.

Code Implementation

class Solution:
    def stringMatching(self, words):
        result = []
        for i, word in enumerate(words):
            for j, other in enumerate(words):
                if i != j and word in other:
                    result.append(word)
                    break
        return result
      

class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        vector<string> result;
        for (int i = 0; i < words.size(); ++i) {
            for (int j = 0; j < words.size(); ++j) {
                if (i != j && words[j].find(words[i]) != string::npos) {
                    result.push_back(words[i]);
                    break;
                }
            }
        }
        return result;
    }
};
      

import java.util.*;
class Solution {
    public List<String> stringMatching(String[] words) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (i != j && words[j].contains(words[i])) {
                    result.add(words[i]);
                    break;
                }
            }
        }
        return result;
    }
}
      

/**
 * @param {string[]} words
 * @return {string[]}
 */
var stringMatching = function(words) {
    let result = [];
    for (let i = 0; i < words.length; i++) {
        for (let j = 0; j < words.length; j++) {
            if (i !== j && words[j].includes(words[i])) {
                result.push(words[i]);
                break;
            }
        }
    }
    return result;
};