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

Approach 01:

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        vector<string> substrings;  // Stores words that are substrings of other words

        for (const string& smallerWord : words) {
            for (const string& largerWord : words) {
                // Check if the smaller word is a substring of the larger word
                if (smallerWord.size() < largerWord.size() && largerWord.find(smallerWord) != string::npos) {
                    substrings.push_back(smallerWord);
                    break;  // No need to check further once found
                }
            }
        }

        return substrings;
    }
};

class Solution:
    def stringMatching(self, words: list[str]) -> list[str]:
        substrings = []  # Stores words that are substrings of other words

        for smallerWord in words:
            for largerWord in words:
                # Check if the smaller word is a substring of the larger word
                if len(smallerWord) < len(largerWord) and largerWord.find(smallerWord) != -1:
                    substrings.append(smallerWord)
                    break  # No need to check further once found

        return substrings

Time Complexity:

• Nested Loop Over Words:

  The algorithm uses a nested loop, where each word is compared with every other word. This contributes \( O(n^2) \), where \( n \) is the number of words in the words array.

• Substring Check:

  For each pair of words, the substring check (find) takes \( O(m) \) time, where \( m \) is the average length of the larger word.

• Overall Time Complexity:

  \( O(n^2 \cdot m) \), combining the nested loop and substring checks.

Space Complexity:

• Output Storage:

  The space used for the substrings vector depends on the number of words that are substrings. In the worst case, it requires \( O(n) \) space.

• Auxiliary Variables:

  Constant space is used for loop variables and temporary references.

• Overall Space Complexity:

  \( O(n) \), dominated by the space used for storing the results.