# String Matching in an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/string-matching-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/string-matching-in-an-array
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** Array, String
---
## Problem
Given an array of string `words`, return all strings in`words`that are a substring of another word. You can return the answer in **any order**.

**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 <= 100`
* `1 <= words[i].length <= 30`
* `words[i]` contains only lowercase English letters.
* All the strings of `words` are **unique**.

# Approaches
## Brute-Force Iteration
The most straightforward approach is to compare every string in the array with every other string. We can use nested loops to achieve this. For each pair of distinct strings, `word1` and `word2`, we check if `word1` is a substring of `word2`.
**Time:** O(N^2 * L^2), where N is the number of strings in the `words` array and L is the maximum length of a string. The nested loops run in O(N^2), and the `String.contains()` method can take up to O(L_i * L_j) in the worst case, which simplifies to O(L^2). · **Space:** O(K * L), where K is the number of strings that are substrings of others. In the worst case, this can be O(N * L) to store the results in the set, where N is the total number of words and L is the max length of a word.
**Pros:** Simple to conceptualize and implement.; Works correctly for the given constraints.
**Cons:** Inefficient due to the number of comparisons.; Performs many redundant checks, such as checking if a longer string is a substring of a shorter one.
### Explanation
We iterate through the `words` array with an outer loop (let's say for `word_i`) and an inner loop (for `word_j`). To ensure we are checking against a different word, we skip the case where the indices `i` and `j` are the same. Inside the inner loop, we use the `contains()` method to check if `words[i]` is a substring of `words[j]`. If it is, we've found a match. To avoid adding the same word multiple times to our result (e.g., 'a' could be a substring of 'ba' and 'ca'), we use a `Set` to store the results. After checking all pairs, we convert the set to a list.

```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<String> stringMatching(String[] words) {
        Set<String> result = new HashSet<>();
        int n = words.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                if (words[j].contains(words[i])) {
                    result.add(words[i]);
                    break; 
                }
            }
        }
        return new ArrayList<>(result);
    }
}
```
### Algorithm
- Initialize an empty `Set<String>` named `result` to store the qualifying words.
- Get the total number of words, `n`.
- Use a nested loop structure. The outer loop iterates from `i = 0` to `n-1`.
- The inner loop iterates from `j = 0` to `n-1`.
- Inside the loops, if `i` equals `j`, `continue` to the next iteration.
- Check if `words[j].contains(words[i])`.
- If the condition is true, add `words[i]` to the `result` set and `break` the inner loop to proceed to the next word in the outer loop.
- Finally, convert the `result` set into a `List` and return it.

## Optimized Approach with Sorting
We can improve upon the brute-force approach by making a simple observation: if a string `s1` is a substring of another string `s2`, then the length of `s1` must be less than or equal to the length of `s2`. By sorting the input array of words by their lengths in ascending order, we can eliminate unnecessary comparisons. We only need to check if a word is a substring of words that are longer than it.
**Time:** O(N * logN + N^2 * L^2). The sorting step takes O(N * logN). The nested loops and `contains()` check contribute O(N^2 * L^2), which is the dominant term. While the asymptotic complexity is the same as the brute-force approach, this method is faster in practice because it reduces the number of string comparisons by roughly half. · **Space:** O(N * L) in the worst case for the result list. The space used by the sorting algorithm depends on the implementation; in Java, `Arrays.sort` for objects is a merge sort variant that uses O(N) auxiliary space.
**Pros:** More efficient than the naive brute-force approach by eliminating impossible cases.; The logic is a clear and direct improvement.
**Cons:** The worst-case time complexity remains high and is dominated by the nested loops for string searching.
### Explanation
The first step is to sort the `words` array based on string length. After sorting, we can iterate through the array from `i = 0` to `n-1`. For each `words[i]`, we only need to check it against subsequent words in the array (`words[j]` where `j > i`), as these are guaranteed to be of the same or greater length. If we find that `words[i]` is a substring of any `words[j]`, we add `words[i]` to our result list and can immediately break out of the inner loop to start checking the next word, `words[i+1]`. This avoids duplicate entries in the result list, so we can use a simple `List` instead of a `Set`.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Solution {
    public List<String> stringMatching(String[] words) {
        Arrays.sort(words, Comparator.comparingInt(String::length));
        
        List<String> result = new ArrayList<>();
        int n = words.length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (words[j].contains(words[i])) {
                    result.add(words[i]);
                    break;
                }
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Sort the `words` array in ascending order based on the length of the strings.
- Initialize an empty `List<String>` named `result`.
- Iterate through the sorted array with an index `i` from `0` to `n-1`.
- Start a nested loop with an index `j` from `i+1` to `n-1`.
- Inside the inner loop, check if `words[j].contains(words[i])`.
- If it is a substring, add `words[i]` to the `result` list.
- `break` the inner loop, as we have confirmed `words[i]` is a substring and don't need to check it against other longer words.
- After the loops complete, return the `result` list.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
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

```