C++优选算法 438. 找到字符串中所有字母异位词

1.题目描述

题目分别给出两个字符串s和p，要求在s中找到所有p的异位词，不必考虑顺序比如：
p=abc，则在s中找到这三个字母连一起的字串便可，如abc、acb、bca、bac、cab、cba都行，并且返回这些字串的个数即可。

2.算法思路

我采用的是滑动窗口+哈希表的做法

• 定义两个哈希表，由于没有大写字母，哈希表大小为26，下标则是 字母-‘a’ 就可以得出
• 进窗口：将进入窗口的字母对比是不是在p中出现，如果出现则统计出现个数，使用count来计算
• 判断：固定一个窗口，使窗口的区间范围，不超过p的大小
• 出窗口：如果count>p.size()则出窗口，随后count–即可
• 更新：定义一个ret容器来存储异位词个数，如果count==p.size()放进ret容器即可

3.完整代码

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[26]={0}; // 存储数组pfor (auto a : p) hash1[a - 'a']++;int m=p.size();int hash2[26]={0};for(int left=0,right=0,count=0;right<s.size();right++){//进窗口char in = s[right];if(++hash2[in-'a']<=hash1[in-'a'])count++;//判断if(right-left+1>m){//出窗口char out = s[left++];if(hash2[out-'a']-- <= hash1[out-'a'])count--;}//更新if(m==count)ret.push_back(left);}return ret;}
};