当前位置：首页 > article >正文

【优选算法系列】【专题二滑动窗口】第四节.30. 串联所有单词的子串和76. 最小覆盖子串

article 2024/9/20 23:42:45

文章目录

前言
一、串联所有单词的子串
1.1 题目描述
1.2 题目解析
1.2.1 算法原理
1.2.2 代码编写
1.2.3 题目总结
二、最小覆盖子串
2.1 题目描述
2.2 题目解析
2.2.1 算法原理
2.2.2 代码编写
2.2.3 题目总结
总结

前言

一、串联所有单词的子串

1.1 题目描述

描述：

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串长度相同。

s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以任意顺序返回答案。

提示：

1 <= s.length <= 10^4
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成

示例1：

示例2：

示例3：

1.2 题目解析

1.2.1 算法原理

1.2.2 代码编写

1.3 题目总结

二、最小覆盖子串

2.1 题目描述

描述：

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。