首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

每天一道c编程题,37题,S 中找出包含 T 所有字母的最小子串。

题目要求:给定一个字符串 S 和一个字符串 T,请在 S 中找出包含 T 所有字母的最小子串。

示例:

输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC"

解题思路:

这是一道滑动窗口的题目,我们可以用两个指针 left 和 right 表示窗口的左右边界,用一个哈希表记录 T 中每个字符出现的次数,然后移动右指针,直到窗口中包含了 T 中所有字符,然后移动左指针,缩小窗口大小,直到窗口中不再包含 T 中所有字符,然后再移动右指针,扩大窗口大小,以此类推,直到右指针越界,得到最小子串。

具体实现可以用一个计数器 count 表示当前窗口中包含 T 中字符的个数,用一个变量 minLen 记录当前最小子串的长度,用两个变量 minLeft 和 minRight 记录当前最小子串的左右边界,用一个哈希表记录当前窗口中每个字符出现的次数。

算法步骤:

初始化 left、right 指针,哈希表、计数器 count 以及 minLeft、minRight 和 minLen。

移动 right 指针,扩大窗口,如果当前字符是 T 中的字符,更新哈希表和计数器 count。

当 count 等于 T 中字符的个数时,移动 left 指针,缩小窗口,如果当前字符是 T 中的字符,更新哈希表和计数器 count。

更新最小子串的长度和左右边界。

重复步骤 2、3、4,直到 right 指针越界。

返回最小子串。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20230319A0321R00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券