Domain 1EasyCORE

String Matching in an Array

The problem requires identifying all strings in an array that are substrings of another string within the same array. The input is an array of strings `words`, and the output should be a list of strings from `words` that appear as substrings in any other string in the array. The constraints specify that the length of the array and each string is relatively small, but we need to ensure our solution is efficient.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

1408. String Matching in an Array

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 63.7%


Problem Breakdown

The problem requires identifying all strings in an array that are substrings of another string within the same array. The input is an array of strings words, and the output should be a list of strings from words that appear as substrings in any other string in the array. The constraints specify that the length of the array and each string is relatively small, but we need to ensure our solution is efficient.

Intuition

A brute-force approach would involve checking every pair of strings in the array to see if one is a substring of the other. This would result in a time complexity of O(n^2 * m), where n is the number of words and m is the average length of the words, which could be inefficient given the constraints.

A better approach involves sorting the array by string length. Once sorted, we only need to check if each word is a substring of any subsequent word in the sorted list. This reduces the number of comparisons needed because shorter strings are more likely to be substrings of longer strings that come after them in the sorted order.

Approach

  1. Sort the Array: Sort the array words by the length of the strings.
  2. Iterate and Check Substrings: Iterate through the sorted array and for each word, check if it is a substring of any subsequent word in the array.
  3. Collect Results: If a word is found to be a substring, add it to the result list.

The sorting step ensures that we only need to compare each word with longer words that come after it, reducing unnecessary comparisons.

Complexity Analysis

  • Time Complexity: O(n^2 * m), where n is the number of words and m is the average length of the words. The sorting step takes O(n log n), but the substring checks dominate the complexity.
  • Space Complexity: O(n) for storing the result list, assuming all words could potentially be substrings.

Solution

def stringMatching(words):
    # Sort words by their lengths
    words.sort(key=len)
    
    result = []
    # Iterate through each word in the sorted list
    for i in range(len(words)):
        # Check if the current word is a substring of any subsequent word
        for j in range(i + 1, len(words)):
            if words[i] in words[j]:
                result.append(words[i])
                break
    
    return result

Edge Cases Handled

  • Empty Input: If the input array is empty, the function will return an empty list.
  • Single Word: If there’s only one word in the array, it cannot be a substring of any other word, so the function will return an empty list.
  • All Words Unique: The problem guarantees that all words are unique, so we don’t need to handle duplicates.