String Matching in an Array

You are given an array of strings words, and you need to find all the strings that are substrings of another string in the same array.

Approach

  1. Iterate through the words array.
  2. For each word, check if it is a substring of any other word in the array.
  3. If a word is a substring of another word, add it to the result list.
  4. Return the result list.

Here’s the code:

1
2
3
4
5
6
7
8
9

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        result = []
        for word in words:
            for other_word in words:
                if word != other_word and word in other_word:
                    result.append(word)
                    break
        return result

Example

Let’s take words = ["mass","as","hero","superhero"] as an example:

  • "as" is a substring of "mass", so add it to the result.
  • "hero" is a substring of "superhero", so add it to the result.

So the output will be ["as","hero"].

This solution checks each word against all other words, resulting in a time complexity of O(n^2 * m), where n is the number of words, and m is the maximum length of a word. This is acceptable for the given constraints.