大家好,我就是那个在B站讲算法的「华南溜达虎」。
不少同学都有大厂情节,今天看到一位同学入职大厂后一个月彻底对大厂祛魅,这位同学表示已经连续两周凌晨以后下班了,人已经懵了,国庆节买的快递至今都懒得拆,家里乱成一团也没精力收拾,家人也很久没联系了,好朋友的微信被淹没在一堆消息里还没回,到家就是躺着,感觉很久没有自己的生活了。
不少同学也有类似的感受,有人说已经连续三个月凌晨两三点钟下班了。也有同学说入职字节第十天就扛不住了,已离职。也有来自医院的肿瘤科医生评论道,他的病人里已有不少大厂员工,建议大家一定要睡够6个小时,内耗也很伤身体,一定要找个体育活动来发泄一下。工作再忙,大家还是要注意身体,毕竟身体是一切的基础,疾病离我们并不远。
25届秋招已经开始了,我组织了一个秋招群,大家可以交流学习心得、面试经验,分享工作机会,有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档,以及投递入口,每天都会更新,大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招!计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传,今天我们来分享一道高频面试题「最小覆盖子串」。
题目描述
给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
注意:
对于 t
中重复字符,我们寻找的子字符串中该字符数量必须不少于t
中该字符数量。如果 s
中存在这样的子串,我们保证它是唯一的答案。
举个例子:
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
思路解析
本题是经典的滑动窗口类型,解决这类问题的关键是窗口左右边界的滑动策略。
定义hash
表u_mapT
保存字符串t
中字符的频率,hash
表u_mapWindow
保存滑动窗口中字符出现的次数,left
保存窗口的左边界,right
保存窗口的右边界,resStart
保存最小候选窗口的起点,resLen
保存最小候选窗口长度。
窗口滑动策略如下:
当
u_mapT
中的元素不全在u_mapWindow
中,窗口右边界right
向右滑动,并更新u_mapWindow[s[right]]++
,直到u_mapT
中的元素全在u_mapWindow
中。当
u_mapT
中的元素全在u_mapWindow
中,更新最小候选窗口的起点resStart
和最小候选窗口长度resLen
,更新u_mapWindow[s[left]]--
且窗口左边界left
向右滑,直到u_mapT
中的元素不全在u_mapWindow
中,进入步骤1
。
根据上面的策略我们可以获得以s
任意位置为左边界(枚举左边界)所有满足条件的候选窗口,只需要把其中最短的一个窗口返回即可。
这里在判断u_mapT
中的元素是否完全在u_mapWindow
中并没有采用遍历u_mapT
对其中的元素一个个去u_mapWindow
中比较。而是借用了一个整型变量tInWindow
在窗口滑动的过程中就对窗口中字符情况进行统计,大大节省了每次判断都要去遍历hash
表的时间。
下面我们给出c++和python的两种代码实现。
C++代码
class Solution {
public:
string minWindow(string s, string t) {
int s_len = s.length();
int t_len = t.length();
if (s_len == 0 || t_len == 0) {
return "";
}
//保存t中字符出现的次数
unordered_map<char, int> u_mapT;
//保存window中的字符出现的次数
unordered_map<char, int> u_mapWindow;
//统计t中的字符
for (int i = 0; i < t_len; ++i) {
u_mapT[t[i]]++;
}
//t中不重复字符的个数
int tCount = u_mapT.size();
//window完全包含t中不重复字符的数量
int tInWindow = 0;
int resStart = 0, resLen = INT_MAX;
int left = 0, right = 0;
while (right < s_len) {
u_mapWindow[s[right]]++;
//假设字符a在t和window中出现的次数相等,就增加tInWindow的计数
if (u_mapT.count(s[right]) && u_mapWindow[s[right]] == u_mapT[s[right]]) {
++tInWindow;
}
while (tInWindow == tCount) {
//窗口的大小小于已保存的最小长度,更新最小长度
if (right - left + 1 < resLen) {
resStart = left;
resLen = right - left + 1;
}
//右移窗口左边界,缩小窗口
u_mapWindow[s[left]]--;
if (u_mapT.count(s[left]) && u_mapT[s[left]] > u_mapWindow[s[left]]) {
--tInWindow;
}
++left;
}
++right;
}
if (resLen == INT_MAX) return "";
return s.substr(resStart, resLen);
}
};
python代码
class Solution:
def minWindow(self, s: str, t: str) -> str:
s_len = len(s)
t_len = len(t)
if s_len == 0 or t_len == 0:
return ""
#保存t中字符出现的次数
u_mapT = defaultdict(int)
#保存window中的字符出现的次数
u_mapWindow = defaultdict(int)
#统计t中的字符
for char in t:
u_mapT[char] += 1
#t中不重复字符的个数
tCount = len(u_mapT)
#window完全包含t中不重复字符的数量
tInWindow = 0
resStart, resLen = 0, float('inf')
left, right = 0, 0
while right < s_len:
u_mapWindow[s[right]] += 1
#假设字符a在t和window中出现的次数相等,就增加tInWindow的计数
if s[right] in u_mapT and u_mapWindow[s[right]] == u_mapT[s[right]]:
tInWindow += 1
while tInWindow == tCount:
#窗口的大小小于已保存的最小长度,更新最小长度
if right - left + 1 < resLen:
resStart = left
resLen = right - left + 1
#右移窗口左边界,缩小窗口
u_mapWindow[s[left]] -= 1
if s[left] in u_mapT and u_mapWindow[s[left]] < u_mapT[s[left]]:
tInWindow -= 1
left += 1
right += 1
if resLen == float('inf'):
return ""
return s[resStart:resStart + resLen]
复杂度分析
时间复杂度: 因为使用变量tInWindow
提前预先保存了window
中是否包含t
的字符,并且只需要遍历一遍s
和t
,所以时间复杂度为O(m + n),其中m
是s
的长度,n
是t
的长度。
空间复杂度: 使用了两个hash
表,具体的复杂度和字符集的大小有关。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦!
https://leetcode.cn/premium/?promoChannel=ldtiger ,年度会员有效期比官网多俩月,季度会员有效期比官网多两个星期,还有专属福利,需要的读者朋友可以找我了解。
今天的分享就到这里,希望大家能有所收获!