力扣76.最小覆盖子串
力扣76.最小覆盖子串[*] 用哈希表记录每个字母出现次数
[*]枚举右端点 判断是否能全覆盖
[*]如果可以 而且更短 就更新
[*]j ++缩小区间再判断
[*] class Solution {
bool is_covered(int cnt_s[], int cnt_t[]) {
for (int i = 'A'; i <= 'Z'; i++) {
if (cnt_s < cnt_t) {
return false;
}
}
for (int i = 'a'; i <= 'z'; i++) {
if (cnt_s < cnt_t) {
return false;
}
}
return true;
}
public:
string minWindow(string s, string t) {
int cnt_s{}, cnt_t{};
int n = s.size(),res=n;
int st=-1,ed=n;
for(auto c:t)
cnt_t ++;
for(int i=0,j=0;i<n;i++)
{
cnt_s] ++;
while(is_covered(cnt_s,cnt_t))
{
if(i - j < ed - st)
{
ed = i;
st = j;
}
cnt_s] -- ;
}
}
return st < 0 ? "" : s.substr(st, ed -st + 1);
}
};
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
页:
[1]