String Matching in an Array

Difficulty: Easy | Acceptance: 69.80% | Paid: No Topics: Array, String, String Matching

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

A substring is a contiguous sequence of characters within a string.

• Examples
• Constraints
• Brute Force
• Sorting by Length

Examples

Example 1

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

Example 2

Input: words = ["leetcode","et","code"]
Output: ["et","code"]
Explanation: "et" and "code" are both substrings of "leetcode".

Example 3

Input: words = ["blue","green","bu"]
Output: []
Explanation: No string is a substring of another.

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 30
words[i] consists of lowercase English letters.
All strings in words are distinct.

Brute Force

Intuition For each word, check if it is a substring of any other word in the array using nested loops.

Steps

• Initialize an empty result list
• For each word in the array, compare it with every other word
• If the current word is a substring of another word, add it to the result
• Return the result list

from typing import List

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        result = []
        n = len(words)
        for i in range(n):
            for j in range(n):
                if i != j and words[i] in words[j]:
                    result.append(words[i])
                    break
        return result

Complexity

• Time: O(n² × m) where n is the number of words and m is the average length of words
• Space: O(n) for the result array
• Notes: Simple and straightforward approach

Sorting by Length

Intuition Sort words by length so that shorter words are checked against longer words, reducing unnecessary comparisons.

Steps

• Sort the words array by length
• For each word at index i, check if it’s a substring of any word at index j > i
• If found, add the word to the result
• Return the result list

from typing import List

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        words.sort(key=len)
        result = []
        n = len(words)
        for i in range(n):
            for j in range(i + 1, n):
                if words[i] in words[j]:
                    result.append(words[i])
                    break
        return result

Complexity

• Time: O(n² × m + n log n) where n is the number of words and m is the average length of words
• Space: O(n) for the result array (sorting is in-place)
• Notes: Slightly optimized by avoiding redundant comparisons