What is the main pattern in the String Matching in an Array problem?

The main pattern is array plus string: you must check which strings in the array are substrings of other strings.

Can I return the substrings in any order?

Yes, the output can be in any order as long as it contains all strings that are substrings of another word.

Is using built-in substring functions acceptable?

Yes, built-in functions are fine for brute force checks, though KMP can improve efficiency for larger arrays.

What is the time complexity of the brute force solution?

It is O(m^2 \times n), where m is the number of strings and n is the maximum length of a string.

How does GhostInterview assist with this problem?

It guides you to apply pairwise substring checks, consider optimizations, and correctly manage duplicates in results.

#1408

Easy

auto_awesome数组·string

LeetCode 题解工作台

数组中的字符串匹配

给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按任意顺序返回 words 中是其他单词的子字符串的所有单词。示例 1：输入： words = ["mass","as","hero","superhero"] 输出： ["as","hero"] 解释： "a…

数组字符串字符串匹配

题目描述

给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按任意顺序返回 words 中是其他单词的子字符串的所有单词。

示例 1：

输入：words = ["mass","as","hero","superhero"]
输出：["as","hero"]
解释："as" 是 "mass" 的子字符串，"hero" 是 "superhero" 的子字符串。
["hero","as"] 也是有效的答案。

示例 2：

输入：words = ["leetcode","et","code"]
输出：["et","code"]
解释："et" 和 "code" 都是 "leetcode" 的子字符串。

示例 3：

输入：words = ["blue","green","bu"]
输出：[]

提示：

1 <= words.length <= 100
1 <= words[i].length <= 30
words[i] 仅包含小写英文字母。
题目数据保证 words 的每个字符串都是独一无二的。

lightbulb

解题思路

方法一：暴力枚举

我们直接枚举所有的字符串 $words[i]$ ，判断其是否为其他字符串的子串，如果是，将其加入答案。

时间复杂度 $O(n^3)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串数组的长度。

1

2

3

4

5

6

7

8

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        ans = []
        for i, s in enumerate(words):
            if any(i != j and s in t for j, t in enumerate(words)):
                ans.append(s)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(m^2 \times n) because each of the m strings is compared with every other string, and each comparison may scan up to n characters. Space complexity is O(m^2 \times n) when storing substring results, especially if using sets to avoid duplicates.
空间	O(m^2 \times n)

psychology

面试官常问的追问

外企场景

question_mark
Check if candidates attempt naive pairwise comparisons or optimize using sorting by length.
question_mark
Observe if candidates consider substring edge cases like identical or nested substrings.
question_mark
Listen for discussion on using string search algorithms such as KMP to improve efficiency.

warning

常见陷阱

外企场景

error
Failing to account for all pairs, missing substrings contained in multiple words.
error
Returning duplicates if using lists instead of sets for results.
error
Ignoring constraints and attempting unnecessary optimizations for small arrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return substrings that appear in at least k other strings instead of just one.
arrow_right_alt
Count the total number of substring occurrences across all words instead of returning the words.
arrow_right_alt
Find substrings that are both prefixes and suffixes of other words, combining array plus string logic.

help

常见问题

外企场景

继续练习

#1023 驼峰式匹配 #2185 统计包含给定前缀的字符串 #2301 替换字符后匹配