从Leetcode 每日一题练习继续讨论：
567. 字符串的排列
567. Permutation in String
题解
本题先统计s1字符串中各个字母的个数。由于要寻找s2中某个子字符串是s1中字母的组合，则使用一个s1长度的滑动窗口在s2字符串上滑动并计数窗口内各个字母的个数，滑动过程中不断将窗口右侧的字母个数加一判断是否与s1匹配，左侧的减一判断是否与s1匹配。用一个变量记录当前窗口中已经匹配的字母的个数，每次滑动后判断匹配的字母个数是否达到26个，达到26个则直接返回true。
代码
class Solution {
public:
bool checkInclusion(string s1, string s2) {
if (s1.size() > s2.size()) {
return false;
}
vector<int> count(26, 0);
vector<int> window(26, 0);
for (char c : s1) {
count[c - 'a']++;
}
for (int i = 0; i < s1.size(); i++) {
window[s2[i] - 'a']++;
}
int matched = 0;
for (int i = 0; i < 26; i++) {
if (window[i] == count[i]) {
matched++;
}
}
if (matched == 26) return true;
// 滑动窗口
for (int right = s1.size(); right < s2.size(); right++) {
int left = right - s1.size();
// 添加右边的新字符
int r = s2[right] - 'a';
window[r]++;
if (window[r] == count[r]) matched++;
else if (window[r] == count[r] + 1) matched--;
// 移除左边的旧字符
int l = s2[left] - 'a';
window[l]--;
if (window[l] == count[l]) matched++;
else if (window[l] == count[l] - 1) matched--;
if (matched == 26) return true;
}
return false;
}
};
