We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

String Matching in an Array

Number: 1524

Difficulty: Easy

Paid? No

Companies: Google, Bloomberg, Amazon

Problem Description

Given an array of unique strings, return all strings that are a substring of another word in the array.

Key Insights

  • Iterate over each word and check against every other word in the list.
  • Use substring checking (e.g., using "in" in Python, "includes" in JavaScript, or string find methods in C++ and Java).
  • The array is small (maximum length = 100) and each string length is bounded (≤ 30), so a simple O(n² * m) solution is acceptable.
  • Avoid duplicate checking by ensuring indices are not the same.

Space and Time Complexity

Time Complexity: O(n² * m), where n is the number of words and m is the maximum word length. Space Complexity: O(n) for the result list.

Solution

The approach is to use nested loops: for each word in the array, compare it with every other word to check if it appears as a substring. When a match is found, add the word to the result and break out of the inner loop to avoid redundant checks. This algorithm leverages built-in substring utilities of the programming language used.

Code Solutions

def string_matching(words):
    # Initialize the list to collect result words that are substrings of another word.
    result = []
    # Loop through each word in the list.
    for i in range(len(words)):
        # Compare with every other word.
        for j in range(len(words)):
            # Check that we're not comparing the same word and that words[i] is a substring of words[j]
            if i != j and words[i] in words[j]:
                result.append(words[i])
                break  # Move to the next word after a valid match is found.
    return result

# Example usage:
words = ["mass", "as", "hero", "superhero"]
print(string_matching(words))
← Back to All Questions