首页 > 试题广场 >

最小覆盖子串

[编程题]最小覆盖子串
  • 热度指数：76744 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解


给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。

数据范围：，保证s和t字符串中仅包含大小写英文字母
要求：进阶：空间复杂度 ， 时间复杂度
例如：



找出的最短子串为.

注意：
如果 s 中没有包含 t 中所有字符的子串，返回空字符串 “”；
满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。

示例1

输入

"XDOYEZODEYXNZ","XYZ"

输出

"YXNZ"
示例2

输入

"abcAbA","AA"

输出

"AbA"
算法知识视频讲解
开通博客
头像 蒙牛麦片
发表于 2021-07-16 18:00:19
精华题解 NC28 最小覆盖子串 题意分析： 有字符串S和T，在S中找出包含T的所有字符的最短的子串 示例：S = "XDOYEZODEYXNZ"，T = "XYZ" S有多个子串包含XYZ，如XDOYEZ，YXNZ等等，其中YXNZ是最小的。 题解一（暴力）： 只要枚 展开全文
去ta的博客 赞 (40) 回复(4) 收起
头像 牛客题解官
发表于 2022-04-22 13:03:37
精华题解 题目主要信息： 在S字符串中找到包含T字符串所有字符的最小连续子串 两个字符串仅包含大小写字母 如果S中没有包含T中所有字符的子串，返回空字符串""，若有，则存在唯一最短 举一反三： 学习完本题的思路你可以解决如下题目： BM92. 最长无重复数组 方法：哈希表匹配（推荐使用） 知识点1：滑动窗 展开全文
去ta的博客 赞 (21) 回复(5) 收起
头像 牛一霸
发表于 2021-07-10 22:26:39
精华题解 题目：最小覆盖子串 描述：给出两个字符串S和T，要求在O(n)的时间复杂度内在S中找出最短的包含T中所有字符的子串。 例如：S="XDOYEZODEYXNZ"，T="XYZ"找出的最短子串为"YXNZ". 注意：如果S中没有包含 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 华科不平凡
发表于 2020-09-01 18:21:03
这道题目用到了滑动窗口这一大杀器，它可以解决如下问题： 最小覆盖子串（LeetCode76） 字符串排列（LeetCode567） 统计字母异位词（LeetCode438） 最长无重复子串（LeetCode3） 滑动窗口的基本思想： 用两个字典分别维护窗口中字符的统计数量、以及被求解子串中字符 展开全文
去ta的博客 赞 (27) 回复(3) 收起
头像 LifelongCode
发表于 2021-02-03 21:21:53
解法1：滑动窗口 转载链接：https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-ji-bai-liao-100de-javayong-hu-/思路：新建一个needs[255] 展开全文
去ta的博客 赞 (12) 回复(2) 收起
头像 十块大洋。
发表于 2021-09-27 19:30:43
初始化左右指针begin= end= 0，把索引区间 [begin, end] 称为一个「窗口」。 不断地增加end指针扩大窗口 [begin, end] ，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。 此时，停止增加end，转而不断增加 begin 指针缩小窗口 [begin, end 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 xqxls
发表于 2021-12-12 20:04:53
题意整理 给出两个字符串s和t，要求在s中找出最短的包含t中所有字符的连续子串。 方法一（暴力循环） 1.解题思路 首先统计T中所有字符出现次数，记录在map1中。 然后两层循环遍历S中所有连续子串，对每一个子串，统计字符出现次数，记录在map2中。 每次判断某个子串是否包含t中所有字符，如果 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 猫头鹰啊猫头鹰
发表于 2021-04-12 20:52:35
来个JAVA版本的，思路都一样 import java.util.*; public class Solution {     /**      *  &nbs 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 牛客995030854号
发表于 2022-04-27 10:45:52
解题思路 哈希表+双指针---窗口滑动问题 1，map记录目标子串中需要的字符和相应的个数。 2,右指针滑动的时候，检查是否是所需需要的，是需要的就修改map中的所需个数。 3，找到所需的子串的时候，就与上次找到的进行比较，更短则更新，这时候考虑左指针的移动，如果左指针指向的字符是所需要的，需要将 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 牛客432959891号
发表于 2022-08-30 18:46:56
class Solution:     def minWindow(self , S: str, T: str) -> str:     展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Seauning
发表于 2022-05-01 10:17:06
看注释理解 题目：https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac /** * * @param S string字符串 * @param T string字符串 * @return str 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 tonngw
发表于 2022-03-06 13:07:21
滑动窗口算法 / 双指针算法 定义两个哈希表，一个 hs 用于存储窗口 [i, j] 中字符出现的次数，一个 ht 用于存储字符串 t 中每个字符出现的次数。 定义一个变量 cnt 用于记录窗口中包含字符串 t 的有效字符个数（多的不算）。 先将 t 中每个字符和出现次数存入哈希表，然后遍历字符串 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 haishen2022
发表于 2022-10-07 10:26:37
评论区巴拉出来的 ，还是想了很久 char* minWindow(char* S, char* T ) {     /*hash T字符串*/    &n 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

字符串 哈希 双指针
难度：
143条回答 28511浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号