力扣438——找到字符串中的所有字母异位词
我们使用定长的滑动窗口的方法来解决这道题
Python：
from collections import Counter
class Solution:
def findAnagrams(self, s, p):
ans = []
p_counter = Counter(p)
window_counter = Counter(s[:len(p)])
if window_counter == p_counter:
ans.append(0)
for right in range(len(p), len(s)):
left = right - len(p)
window_counter[s[right]] += 1
window_counter[s[left]] -= 1
if window_counter[s[left]] == 0:
del window_counter[s[left]]
if window_counter == p_counter:
ans.append(left + 1)
return ans
C++:
class Solution {
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> ans;
vector<int> cnt_p(26);
vector<int> cnt_s(26);
for(char c:p)
cnt_p[c-'a']++;
for(int right = 0;right < s.length();right++)
{
cnt_s[s[right] - 'a']++;
int left = right - p.length() + 1;
if(left < 0)
continue;
if(cnt_s == cnt_p)
ans.push_back(left);
cnt_s[s[left] - 'a']--;
}
return ans;
/*
vector<int> ans;
array<int, 26> cnt_p{}; // 统计 p 的每种字母的出现次数
array<int, 26> cnt_s{}; // 统计 s 的长为 p.length() 的子串 s' 的每种字母的出现次数
for (char c : p) {
cnt_p[c - 'a']++;
}
for (int right = 0; right < s.length(); right++) {
cnt_s[s[right] - 'a']++; // 右端点字母进入窗口
int left = right - p.length() + 1;
if (left < 0) { // 窗口长度不足 p.length()
continue;
}
if (cnt_s == cnt_p) { // s' 和 p 的每种字母的出现次数都相同
ans.push_back(left); // s' 左端点下标加入答案
}
cnt_s[s[left] - 'a']--; // 左端点字母离开窗口
}
return ans;
*/
}
};
C:
int* findAnagrams(char* s, char* p, int* returnSize) {
int * ans = malloc(strlen(s) * sizeof(int));
*returnSize = 0;
int cnt_p[26] = {};
int cnt_s[26] = {};
for(int i = 0;p[i];i++)
{
cnt_p[p[i]-'a']++;
}
for(int right = 0;s[right];right++)
{
cnt_s[s[right]-'a']++;
int left = right - strlen(p) + 1;
if (left < 0)
continue;
/*
memcmp是 C 语言中的一个函数，用于比较两个内存区域的内容。在这里，它用于比较两个长度为 26 的整数数组 cnt_s 和 cnt_p。
cnt_p 数组存储了字符串 p 中每种字母（假设只考虑小写字母，所以用 26 表示 26 个字母）的出现次数。
cnt_s 数组存储了当前正在检查的字符串 s 的子串中每种字母的出现次数。
当 memcmp 返回 0 时，表示两个数组的内容完全相同。这意味着当前子串（窗口）中的字母出现次数与字符串 p 的字母出现次数完全一致，即找到了一个与 p 为字母异位词的子串。
*/
if(memcmp(cnt_s,cnt_p,sizeof(cnt_s))==0)
ans[(*returnSize)++] = left;
cnt_s[s[left]-'a']--;
}
return ans;
/*
int* ans = malloc(strlen(s) * sizeof(int));
*returnSize = 0;
int cnt_p[26] = {}; // 统计 p 的每种字母的出现次数
int cnt_s[26] = {}; // 统计 s 的长为 n 的子串 s' 的每种字母的出现次数
int n = 0;
for (; p[n]; n++) {
cnt_p[p[n] - 'a']++; // 统计 p 的字母
}
for (int right = 0; s[right]; right++) {
cnt_s[s[right] - 'a']++; // 右端点字母进入窗口
int left = right - n + 1;
if (left < 0) { // 窗口长度不足 n
continue;
}
if (memcmp(cnt_s, cnt_p, sizeof(cnt_s)) == 0) { // s' 和 p 的每种字母的出现次数都相同
ans[(*returnSize)++] = left; // s' 左端点下标加入答案
}
cnt_s[s[left] - 'a']--; // 左端点字母离开窗口
}
return ans;
*/
}