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

2024-06-06 HGNULB 约 6 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

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

题意分析

给定一个字符串数组 words，要找出其中所有「是另一个字符串的子串」的字符串，按任意顺序返回。这里的子串指连续的一段字符，不是子序列。

三个细节要抠清楚。第一，判断的对象是数组内部的元素两两之间，不是与外部字符串比较。第二，「另一个」意味着不能拿自己和自己比——每个字符串都是自己的子串，若允许自比，所有元素都会被选中。第三，返回的是被包含的那些串，不是包含别人的那些串，方向不能反。

题目保证 words 中的字符串互不相同，这条保证非常有用：它意味着两个长度相同的不同字符串之间不可能存在包含关系（等长且互为子串就必然相等）。这一点直接支撑了后面按长度排序的优化。

约束里 words.length 最多 100，每个字符串长度最多 30，全是小写字母。规模极小，$O(n^2 L)$ 的朴素两两比较只有 100 × 100 × 30 = 3 × 10^5 次字符操作，完全够用。这组约束在明示：不需要 KMP、不需要后缀自动机，直接暴力比较即可，把力气花在正确性和边界上。

边界要留意四点：一个字符串可能同时是多个更长串的子串，但只能被加入结果一次；结果的顺序不限；数组可能没有任何满足条件的元素，此时返回空列表；不要把自身算作自身的子串。

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

核心思路

若 short 是另一个字符串 long 的子串，则 len(short) <= len(long)。题目又保证数组内字符串互不相同，所以这里实际有 len(short) < len(long)。

因此先按长度升序排序。对位置 i，只需检查右侧的 j > i：左侧字符串不会更长，自己也被自然排除。子串判定直接使用 Java 的 contains 和 Go 的 strings.Contains，题目给出的字符串长度很小，不需要自行实现 KMP。

循环不变量是：开始处理 i 时，[0, i) 中的字符串已经被正确分类；words[i] 一旦找到一个包含它的右侧字符串，就加入答案并立即 break，所以每个输入字符串最多出现一次。

正确性分两边看：算法加入的字符串都有一个实际包含它的右侧字符串，因此不会误加；若某字符串确实是另一个字符串的子串，包含它的字符串一定更长、排序后一定在右侧，内层循环最终会检查到，因此不会漏掉。

解题步骤

按字符串长度升序排序；等长元素的相对次序不影响结果。

外层枚举 i，内层只枚举 j = i + 1 .. n - 1。

若 words[j].contains(words[i])，记录 words[i] 并结束本轮内层循环。

返回结果；题目允许任意顺序，无需恢复原数组次序。

例如 ["mass", "as", "hero", "superhero"] 排序后为 ["as", "mass", "hero", "superhero"]。"as" 被 "mass" 包含，"hero" 被 "superhero" 包含，答案为 ["as", "hero"]。

边界反例：["a", "ab", "abc"] 中 "a" 被两个字符串包含，但只能加入一次；["blue", "bu"] 中 "bu" 不是连续子串，结果为空；单元素数组的答案也为空。

代码实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

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
}

复杂度分析

时间复杂度：排序为 $O(n \log n)$；最多检查 $O(n^2)$ 对字符串。若以朴素子串匹配的最坏 $O(L^2)$ 计，总上界为 $O(n^2 L^2)$，其中 $L$ 是最大字符串长度。

空间复杂度：不计返回结果，Java 对象数组排序需要 $O(n)$ 辅助空间，Go 排序栈为 $O(\log n)$；答案最多保存 $n$ 个字符串引用。排序会原地改变 words 的顺序。

关键点总结

“是另一个字符串的子串”先给出长度必要条件，再利用元素互异把它加强为严格更短。

长度排序后只向右检查，既过滤更短候选，也避免字符串与自身比较。

子串必须连续；标准库查找足够，手写匹配只会增加边界错误。

命中后立刻 break，无需额外集合去重。

正确性依赖题目保证字符串互不相同；若允许重复，等长副本也可能满足“另一个字符串”。

易错点总结

包含方向写反：应判断 words[j] 是否包含 words[i]。["mass", "as"] 的答案是 "as"，不是 "mass"。

允许与自身比较：每个字符串都是自己的子串，会把所有元素都误加入；内层从 i + 1 开始即可避免。

命中后不结束内层循环：["a", "ab", "abc"] 会把 "a" 加入两次。

按字典序排序后仍只向右扫描：长字符串不一定在短字符串右侧，会漏解；排序键必须是长度。

使用前缀判断代替子串判断："hero" 位于 "superhero" 尾部，startsWith / HasPrefix 会漏掉它。

相似题目

题目	难度	考察点
28. 找出字符串中第一个匹配项的下标	简单	单次子串定位，是本题内层判定的独立练习，也是学 KMP 的入口
392. 判断子序列	简单	子序列不要求连续，双指针即可，正好对照本题「子串必须连续」
524. 通过删除字母匹配到字典里最长单词	中等	在字典中找最长子序列匹配，判定换成子序列且要比较长度与字典序
1233. 删除子文件夹	中等	同为「数组内元素间的包含关系」，但判定是前缀而非任意位置，可先排序再线性扫
14. 最长公共前缀	简单	数组内字符串的前缀比较，训练多串同时扫描的写法
720. 词典中最长的单词	中等	要求每个前缀都在词典中，需要排序后配合集合逐步构建
648. 单词替换	中等	大量前缀查询用字典树把单次查找降到 $O(L)$，是本题规模放大后的正解方向
208. 实现 Trie (前缀树)	中等	前缀检索的底层结构，理解它才能判断何时该从暴力升级
472. 连接词	困难	判断一个词能否由词典中其他词拼成，需要排序 + 字典树 + DP 三者配合
1044. 最长重复子串	困难	单串内找最长重复子串，需要二分答案 + 字符串哈希，是子串问题的高阶形态
718. 最长重复子数组	中等	两串的最长公共连续段，用 DP 求解，体现「连续」约束在 DP 中的表达
459. 重复的子字符串	简单	判断字符串是否由子串重复构成，可用拼接技巧或 KMP 的 next 数组
796. 旋转字符串	简单	把旋转判定化归为「是否为自身拼接的子串」，是子串判定的巧用
187. 重复的DNA序列	中等	定长子串去重计数，用哈希或滚动哈希，展示子串问题的另一类处理方式