---
###### tags: `Leetcode`
---
# Leetcode 1408. String Matching in an Array

[link](https://leetcode.com/problems/string-matching-in-an-array/)

---

Given an array of string words, return all strings in words that is a substring of another word. You can return the answer in any order.

A substring is a contiguous sequence of characters within a string

#### 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.

---

For each words[i], check if it’s a substring of words[j] (0 <= j < N && i != j). Once find a match, we can push words[i] to result and continue to word[i + 1].

#### Solution 1

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        lst = []
        for i, w1 in enumerate(words):
            for j, w2 in enumerate(words):
                if i != j and (w1 in w2):
                    if w1 not in lst: lst.append(w1)

        return lst

O(T): O(n^2)
O(S): O(n)