《算法闯关指南：优选算法--滑动窗口》--15.串联所有单词的子串，16.最小覆盖子串
《算法闯关指南：优选算法--滑动窗口》--15.串联所有单词的子串，16.最小覆盖子串
🔥草莓熊Lotso：个人主页
❄️个人专栏：《C++知识分享》《Linux 入门到实践：零基础也能懂》
✨生活是默默的坚持，毅力是永久的享受。
🎬博主简介：
前言：
聚焦算法题实战，系统讲解三大核心板块：优选算法：剖析动态规划、二分法等高效策略，学会寻找“最优解”。 递归与回溯：掌握问题分解与状态回退，攻克组合、排列等难题。 贪心算法：理解“局部最优”到“全局最优”的思路，解决区间调度等问题 内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。
15. 串联所有单词的子串
题目链接：
题目描述：
题目示例：
解法（滑动窗口+哈希表）：
算法思路：
- 如果我们把每一个单词看成一个个字母，问题就变成了找到【字符串中所有的字母的异位词】。无非就是之前处理的对象是一个个字符，我们这里处理的对象是一个一个的单词。
有以下几点不同：
- 哈希表需要使用 hash<string,int>
- left和right移动的步长是单词的长度(len)
- 滑动窗口执行的次数也是 len 次
C++算法代码：
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ret;
unordered_map<string,int> hash1;//保存words里面所有单词的频次
for(auto &s:words) hash1[s]++;
int len=words[0].size(),m=words.size();
for(int i=0;i<len;i++)//执行len次
{
unordered_map<string,int> hash2;//维护窗口内单词的频次
for(int left=i,right=i,count=0;right+len<=s.size();right+=len)
{
//进窗口+维护count
string in=s.substr(right,len);
hash2[in]++;
if(hash1.count(in)&&hash2[in]<=hash1[in]) count++;
if(right-left+1>len*m)//判断
{
//出窗口+维护count
string out=s.substr(left,len);
if(hash1.count(out)&&hash2[out]<=hash1[out]) count--;
hash2[out]--;
left+=len;
}
if(count==m) ret.push_back(left);//更新结果
}
}
return ret;
}
};算法总结&&笔记展示：
笔记字有点丑，大家见谅：
16. 最小覆盖子串
题目链接：
题目描述：
题目示例：
解法 (滑动窗口+哈希表)：
算法思路：
研究对象是连续的区间，因此可以尝试使用滑动窗口的思想来解决。
如何判断当前窗口的所有字符是符合要求的呢？
- 我们可以使用两个哈希表。其中一个将目标串的信息统计起来，另一个哈希表动态的维护窗口内字符串的信息。
- 当动态哈希表中包含目标串中所有字符，并且对应的个数都不小于目标串的哈希表中各个字符的个数，那么当前的窗口就是一种可行的方案。
算法流程：
1. 定义两个全局的哈希表：hash1用来记录子串的信息，hash2用来记录目标串 t 的信息；
2. 实现一个接口函数，判断当前窗口是否满足要求：
2.1 遍历两个哈希表中对应位置的元素
2.1.1 如果 t 中某个字符的数量大于窗口中字符的数量，也就是 hash2 某个位置大于 hash1 。说迷宫不匹配，返回 false。
2.1.2 如果全部匹配，返回 true。
主函数中：
1.先将 t 的信息放入 hash2 中；
2.初始化一些变量：左右指针：left=0，right=0；目标子串的长度：len=INT_MAX；目标子串的起始位置：retleft；(通过目标子串的起始位置和长度，我们就可以找到结果)
3.当 right 小于字符串 s 的长度时，一直下列循环：
3.1 将当前遍历到的元素扔进 hash1 中；
3.2 检测当前窗口是否满足条件；
3.2.1 如果满足条件：
判断当前窗口是否变小。如果变小：更新长度 len，以及字符串的起始位置 retleft
判断完毕后，将左侧的元素滑出窗口，顺便更新到 hash1；
重复上述两个过程，直到窗口不满足条件；
3.3 right++，遍历下一个元素；
4. 判断 len 的长度是否等于 INT_MAX;
4.1 如果相等，说明没有匹配，返回空串；
4.2 如果不相等，说明匹配，返回 s 中从 retleft 位置往后 len 长度的字符串。
C++算法代码：
初版：
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char,int> hash1;
for(auto &ch:t) hash1[ch]++;
unordered_map<char,int> hash2;
int n=hash1.size(),m=s.size(),len=INT_MAX,reti=0;
for(int left=0,right=0,count=0;right<m;right++)
{
//进窗口+维护count
char in=s[right];
hash2[in]++;
if(hash1.count(in)&&hash2[in]==hash1[in]) count++;
while(count==n)//判断
{
//更新结果
if(right-left+1<len)
{
len=right-left+1;
reti=left;
}
//出窗口+维护count
char out=s[left++];
if(hash1.count(out)&&hash2[out]==hash1[out]) count--;
hash2[out]--;
}
}
return len==INT_MAX?"":s.substr(reti,len);
}
};优化版：
class Solution {
public:
string minWindow(string s, string t) {
int hash1[128] = {0}; // 统计字符串 t 中每⼀个字符的频次
int kinds = 0; // 统计有效字符有多少种
for (auto ch : t)
if (hash1[ch]++ == 0)
kinds++;
int hash2[128] = {0}; // 统计窗⼝内每个字符的频次
int minlen = INT_MAX, begin = -1;
for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
char in = s[right];
if (++hash2[in] == hash1[in]) count++; // 进窗⼝ + 维护 count
while (count == kinds) // 判断条件
{
if (right - left + 1 < minlen) // 更新结果
{
minlen = right - left + 1;
begin = left;
}
char out = s[left++];
if (hash2[out]-- == hash1[out])
count--; // 出窗⼝ + 维护 count
}
}
return begin==-1?"":s.substr(begin, minlen);
}
};算法总结&&笔记展示：
笔记字有点丑，大家见谅：
结尾：
往期回顾：
《算法闯关指南：优选算法--滑动窗口》--14找到字符串中所有字母异位词
结语：本文分享了两个字符串处理算法题解：1.《串联所有单词的子串》采用滑动窗口+哈希表方法，将单词视为字符处理，通过控制窗口步长和频次统计实现高效匹配；2.《最小覆盖子串》通过双哈希表动态维护目标串和窗口字符频次，优化版使用128位数组提升效率。
✨把这些内容吃透超牛的！放松下吧✨ ʕ˘ᴥ˘ʔ づきらど
腾讯云开发者
