数组中的字符串匹配

“数组中的字符串匹配”问题通常指的是：给定一个字符串数组，找出所有是其他字符串子字符串的字符串。可以用编程语言实现这一功能。

示例

输入：

words = ["mass", "as", "hero", "superhero"]

输出：

["as", "hero"]

说明：

• "as" 是 "mass" 的子字符串。
• "hero" 是 "superhero" 的子字符串。

Python 解法

以下是解决该问题的代码：

def stringMatching(words):
    result = []
    for i, word in enumerate(words):
        for j, other_word in enumerate(words):
            if i != j and word in other_word:
                result.append(word)
                break
    return result

# 示例
words = ["mass", "as", "hero", "superhero"]
print(stringMatching(words))

解法说明

1. 遍历所有组合：
   • 使用两个嵌套的 for 循环，检查 word 是否是 other_word 的子字符串。
2. 跳过自身检查：
   • 如果 i == j，直接跳过。
3. 避免重复添加：
   • 如果找到匹配，立即 break，防止重复检查。
4. 时间复杂度：
   • 本解法时间复杂度为 O(n2⋅m)O(n^2 \cdot m)，其中 nn 是数组长度，mm 是字符串的平均长度。

优化解法：排序与单次检查

我们可以通过先对数组按长度排序，减少不必要的比较。

def stringMatching(words):
    words.sort(key=len)  # 按长度排序
    result = []
    for i in range(len(words)):
        for j in range(i + 1, len(words)):  # 只检查比当前字符串长的
            if words[i] in words[j]:
                result.append(words[i])
                break
    return result

# 示例
words = ["mass", "as", "hero", "superhero"]
print(stringMatching(words))

• 排序优势：
  • 只需要检查比当前字符串更长的字符串。
• 时间复杂度：
  • O(nlog⁡n+n2)O(n \log n + n^2)，其中排序为 O(nlog⁡n)O(n \log n)。

你可以根据具体场景，选择合适的实现方法。如果有其他要求或需要进一步解释，随时告诉我！