💬 Discord
Sign In
NeetCode #39LC-1408EasyArrays & Hashing
← Back to All Problems

#39 · #1408 · String Matching in an Array(数组中的字符串匹配)

📌 Problem Statement & Constraints

Given an array of strings words, return all strings that are a substring of another string in the array, in any order. Constraints: 1 <= words.length <= 100, 1 <= words[i].length <= 30; all strings are distinct.

💡 Core Algorithmic Approaches

  1. The input is tiny (at most 100 strings of length at most 30), so an O(n^2) pairwise comparison is perfectly acceptable.
  2. For each word, test whether it occurs as a substring of any other word.
  3. Because the strings are guaranteed distinct, a word can never be a substring of itself, so the index check is only a safety measure.
  4. The straightforward implementation uses in for the substring test, which is efficient in practice.

💻 Benchmark Python3 Implementation

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        res = []
        for i, w in enumerate(words):
            for j, other in enumerate(words):
                if i != j and w in other:  # w is a substring of a different word
                    res.append(w)
                    break                  # no need to check further
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2 * L) where L is the maximum string length, since each substring test is O(L) with efficient string search. With n <= 100 and L <= 30 this is negligible.
💾 Space Complexity
O(1) beyond the output list.

⚠️ Interview Pitfalls & Follow-ups

  • Checking w in w: always true, so every word would be reported. The i != j guard is essential (the distinctness guarantee makes it redundant here, but relying on that is fragile).
  • Forgetting to break: a word could be appended multiple times if it appears in several others.
  • Sorting by length first and only checking longer words: a reasonable optimisation, but unnecessary at these sizes and easy to get wrong.