本节博客是对“最小覆盖子串”题目由暴力求解到滑动窗口的思路解析,有需要借鉴即可。
目录
- 1.题目
- 2.滑动窗口解法
- 3.总结
1.题目
题目链接:LINK
这个题目是困难难度,感觉是一个中等题目的感觉。
首先我肯定想到的是暴力求解的方法,大概就是下面这种思路:
在比较找出的子串是否满足条件时候,可以用有效字符的方法,比如下面代码的count计数。
class Solution {
public:
//暴力求解:string minWindow(string s, string t) {//定义一个哈希表,用来收集t的有关信息string ret = "";int hash_t[128] = {0};for(int i = 0; i < t.size(); i++){hash_t[t[i]]++;}int minlength = 0;for(int left = 0; left < s.size(); left++){int hash_s[128] = {0};int count = 0;for(int right = left; right < s.size(); right++){//进哈希表hash_s[s[right]]++;if(hash_s[s[right]] <= hash_t[s[right]])count++;//有效字符++//判断if(count == t.size() && (minlength==0 || minlength >= right - left + 1)){minlength = right - left + 1;//有结果就把这次的长度更新过来,下一次比较的时候用ret = s.substr(left, minlength);break;}}}return ret;}
};
count有效计数原理:
当我们进哈希数组时候,如果这个字符映射的数组值小于等于hash_t的对应数组,则就是需要的,那么count就++,反之则不是
同理,当我们出字符时候,也是这个道理。
2.滑动窗口解法
但是我们可以发现,left 和 right是可以不用回退一直向前的,这就满足双指针,滑动窗口算法的使用条件
所以,代码可以优化成下面代码:
class Solution {
public:string minWindow(string s, string t) {//统计t的有关信息int hash_t[128] = { 0 };int kinds = 0;for(auto ch : t){if(hash_t[ch]++ == 0)kinds++;}int start = -1;int length = INT_MAX;//统计s的有关信息int hash_s[128] = { 0 };for(int left = 0, right = 0, count = 0; right < s.size(); right++){//进窗口char in = s[right];hash_s[in]++;if(hash_s[in] == hash_t[in])count++;//判断while(count == kinds){//更新结果if(right - left + 1 < length){length = right - left + 1;start = left;}//出窗口char out = s[left];if(hash_s[out] == hash_t[out]) count--;hash_s[out]--;left++;}}if(start == -1)return "";else return s.substr(start, length);}
};
注:这个地方的count计数与暴力求解的计数区别是这里用的是字母种类个数。
3.总结
如果有前面“滑动窗口”的题目铺垫其实这道题并不难,需要用到count计数的优化以及滑动窗口的思想。
EOF