LeetCode 1408. 数组中的字符串匹配

约 4 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节
标签
数组 字符串 字符串匹配

题目描述

✅ 1408. 数组中的字符串匹配

image-20260929082538909

image-20260929082539019

题意分析

给定若干互不相同的小写英文字符串，找出其中所有“是另一个输入字符串的连续子串”的元素。返回被包含的字符串本身，结果顺序不限。

包含位置可以在开头、中间或末尾，但字符必须连续，不能按子序列跳着匹配。一个字符串包含自己不算答案，必须有另一个输入元素作为包含者。

解法：按长度排序 + 子串判断

核心思路

[!blue]

一个字符串若是另一个不同字符串的子串，包含者的长度一定更大：同长度包含只能意味着内容完全相同，而题目保证输入互不相同。因此先按长度升序排序后，每个词可能的包含者都在它右边。

对排序后位置 i，依次检查右侧 j > i 的字符串是否包含它。可以直接使用标准字符串的连续子串查询，不需要为题目的小规模词表额外实现匹配算法。

只要找到一个包含者，当前词就已经满足要求，加入结果后立即停止本轮。它即使被多个更长词包含，也只输出一次；每个输入词只作为外层候选处理一次，因此无需额外集合去重。

长度排序只用于缩小查找方向，不是把“长短关系”当成充分条件，真正入选仍必须通过连续包含判断。排序会改变输入词表顺序，但输出允许任意顺序。

解题步骤

  1. 按字符串长度升序排列输入词表。
  2. 依次把每个位置 i 的字符串作为待筛选对象。
  3. 只检查 j > i 的字符串，用连续子串查询判断是否包含当前词。
  4. 命中就收集当前词并结束本轮查找，最后返回全部入选词。

代码实现

class Solution {
    public List<String> stringMatching(String[] words) {
        // 按长度排序，可能的包含者都在当前位置右侧。
        Arrays.sort(words, Comparator.comparingInt(String::length));
        List<String> answer = new ArrayList<>();

        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                // 命中任意包含者即可，随后结束避免同一词重复输出。
                if (words[j].contains(words[i])) {
                    answer.add(words[i]);
                    break;
                }
            }
        }

        return answer;
    }
}

import (
    "sort"
    "strings"
)

func stringMatching(words []string) []string {
    // 按长度排序，可能的包含者都在当前位置右侧。
    sort.Slice(words, func(i, j int) bool {
        return len(words[i]) < len(words[j])
    })

    answer := make([]string, 0)
    for i := 0; i < len(words); i++ {
        for j := i + 1; j < len(words); j++ {
            // 命中任意包含者即可，随后结束避免同一词重复输出。
            if strings.Contains(words[j], words[i]) {
                answer = append(answer, words[i])
                break
            }
        }
    }
    return answer
}

复杂度分析

设单词数为 $n$，最长词长为 $L$。

  • 时间复杂度：排序为 $O(n\log(n+1))$，另加最多 $O(n^2)$ 次包含查询。按朴素子串比较的最坏代价给出保守上界，总计为 $O(n^2L^2+n\log(n+1))$；具体查询耗时取决于标准库实现。
  • 辅助空间复杂度：Java 对象数组排序需要 $O(n)$，Go 排序栈为 $O(\log(n+1))$；结果另保存至多 $n$ 个字符串引用。

关键点总结

[!green]

  • 输入互异使真正的包含者必须更长，长度排序后只需向右查找。
  • 查询方向是“长串包含当前短串”，输出对象是当前短串。
  • 命中任意包含者后停止，保证同一个词不会重复入选。

易错点总结

[!yellow]

  • 字典序不能代替长度排序，否则包含者可能位于当前词左边。
  • 允许自己与自己比较，会让每个输入词都被错误加入答案。
  • 只做前缀匹配会漏掉位于中间或末尾的子串，子序列匹配又会错误允许不连续字符。
  • 命中后不结束内层循环，可能把同一个词多次写入结果。
  • 长度更大只是候选条件，不能不检查内容就认定包含。

相似题目

题目 难度 关联与区别
28. 找出字符串中第一个匹配项的下标 简单 检查一个单词是否为另一个单词的子串是基础，本题批量对词表进行筛选。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/76873397
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！