对于有关子串
的题目我们使用暴力枚举都是比较轻易做出来的
但是我们注意到此题寻找的是字母异位词,并不是顺序的,所以我们可以使用哈希表
来进行解决这个问题。
我们先创建一个hash1
存储p
的数据
在创建一个hash2
来存放遍历s
的数据
因为对于这题来说暴力算法肯定是超时的,所以我们只讲述思路,
但是这个思路是非常重要的。
我们可以通过暴力解法来优化得到滑动窗口。
知道可以使用滑动窗口来做题我们便可以使用滑动窗口的模板来做题。
class Solution {
public:
bool check(int* hash1, int* hash2)
{
for(int i = 0; i < 26; i++)
if(hash1[i] != hash2[i]) return false;
return true;
}
vector<int> findAnagrams(string s, string p) {
int hash1[26] = { 0 };
for(auto ch : p) hash1[ch - 'a']++;
int hash2[26] = { 0 };
vector<int> ans;
for(int left = 0, right = 0; right < s.size(); right++)
{
//进窗口
char in = s[right];
hash2[in - 'a']++;
//判断
while(right - left + 1 > p.size())
{
char out = s[left++];
hash2[out - 'a']--;
}
//更新结果
if(check(hash1, hash2)) ans.push_back(left);
}
return ans;
}
};
我们发现,每次判断是否要更新结果时都要判断26次,
虽然时间复杂度依旧是O(N),但是我们可以优化一下这个地方。
如何进行优化呢?
我们增加一个计数器,这个计数器用来存放当前窗口有效的元素个数,然后在我们判断是否更新时只需要比较count与p的长度即可。
当然,这个count维护的地方也有一些细节
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int hash1[26] = { 0 };
for(auto ch : p) hash1[ch - 'a']++;
int hash2[26] = { 0 };
vector<int> ans;
for(int left = 0, right = 0, count = 0; right < s.size(); right++)
{
//进窗口
char in = s[right];
if(++hash2[in- 'a'] <= hash1[in - 'a']) count++;
//判断
while(right - left + 1 > p.size())
{
char out = s[left++];
if(hash2[out- 'a']-- <= hash1[out - 'a']) count--;
}
//更新结果
if(count == p.size()) ans.push_back(left);
}
return ans;
}
};