文章目录
- 题目描述
- 算法原理
- 滑动窗口+哈希表
- 代码实现
题目描述
题目链接:438.找到字符串中所有字母异位词
算法原理
滑动窗口+哈希表
- 因为字符串p的异位词的⻓度⼀定与字符串p 的⻓度相同,所以我们可以在字符串s 中构造⼀个⻓度为与字符串p的⻓度相同的滑动窗⼝,并在滑动中维护窗⼝中每种字⺟的数量;
- 当窗⼝中每种字⺟的数量与字符串p 中每种字⺟的数量相同时,则说明当前窗⼝为字符串p的异位词;
- 因此可以⽤两个⼤⼩为26 的数组来模拟哈希表,⼀个来保存s 中的⼦串每个字符出现的个数,另⼀个来保存p中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。
代码实现
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int hash1[26] = { 0 };//统计字符串p中每个字符出现的个数
for(auto ch : p)hash1[ch - 'a']++;
int hash2[26] = { 0 };//统计窗口里面每一个字符出现的个数
vector<int> res;
for(int left = 0,right = 0,count = 0;right < s.size();right++)//1.控制窗口
{
char in = s[right];
if(++hash2[in - 'a'] <= hash1[in - 'a'])count++;//2.进窗口+维护count
while(right - left + 1 > p.size())//3.判断
{
char out = s[left++];
if(hash2[out - 'a']-- <= hash1[out - 'a'])count--;//维护count+出窗口
}
if(count == p.size()) res.push_back(left);//更新结果
}
return res;
}
};