今天是农历除夕，然而近年来年味渐淡，凡有亲朋在，便是好时节，也无需对此日特别注重了。
题目链接：https://leetcode-cn.com/problems/permutation-in-string/
题目
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1
输入： s1 = “ab” s2 = “eidbaooo”
输出： True
解释： s2包含s1的排列之一（“ba”）
示例2
输入： s1= “ab” s2 = “eidboaoo”
输出： False
数据范围
- 输入的字符串只包含小写字母
- 两个字符串的长度都在 [1, 10,000] 之间
分析
s2的某个子串包含s1的排列，即s2的某个子串中字母分布与s1完全一样。
我最先想到使用一个集合来保存s1的所有字母，使用滑动窗口
left ~ right遍历s2中的每个子串：
- 当某个字符不在集合中时，
left = right = right + 1- 当某个字符在集合中时，从集合中删除该字符
按照上面的规则，当某个子串完全包含s1中的所有字符时，遍历完这个子串之后集合就变为空。
我竟能想到如此NT的做法！WA了一次后发现，当某个字符不在集合中时直接使
left = right = right + 1可能直接使得窗口向右滑动很多个距离，忽略了一些子串。WA的测试用例如下：
“adc”
“dcda”
可以看到，当窗口
right == 2时，这个字符d已经在第0位被删除，故认为此字符不在s1中，窗口直接指向最后一个字符，输出为False。然而，这个d是在最开始被占用掉了，它实际上存在于s1中，窗口不应如此移动。
WA代码1
class Solution {
public:
bool checkInclusion(string s1, string s2) {
multiset<char> s1_set;
multiset<char> tmp;
multiset<char>::iterator itr;
for (auto t : s1)
{
s1_set.insert(t);
}
tmp = s1_set;
int left = 0;
int right = 0;
while (right < s2.size())
{
itr = tmp.find(s2[right]);
if (itr != tmp.end()) // 此字符存在
{
tmp.erase(itr); // 删除此字符
if (tmp.empty()) // 删完了
return true;
right++; // 还没删完，窗口扩张
}
else // 此字符不存在
{
left = right = right + 1;
tmp = s1_set;
}
}
return false;
}
};
那么，窗口应该如何移动呢？我的思路还保持在使用集合上。
首先，窗口移动时只有边界字符有所进出，故不需要对集合重新赋值，只需要不断地
erase和insert即可。当
right所指向的字符不存在时，需要判断左边界和右边界是否相等，因为若此时左边界不等于右边界，该right所指向的字符可能只是被窗口内的某个元素占用了，我们应该滑动左边界，释放左边界占用的元素（即重新加入集合），而不是像上面的WA代码这样使左右边界进行了跳跃。而若左右边界相等，就同时指向下一个元素即可。这样能写出第一个AC代码：
AC代码1
class Solution {
public:
bool checkInclusion(string s1, string s2) {
multiset<char> s1_set;
multiset<char> tmp;
multiset<char>::iterator itr;
for (auto t : s1)
{
s1_set.insert(t);
}
tmp = s1_set;
int left = 0;
int right = 0;
while (right < s2.size())
{
itr = tmp.find(s2[right]);
if (itr != tmp.end()) // 此字符存在
{
tmp.erase(itr); // 删除此字符
if (tmp.empty()) // 删完了
return true;
right++; // 还没删完，窗口扩张
}
else // 此字符不存在
{
if (left == right)
{
left = right = right + 1;
}
else
{
tmp.insert(s2[left]);
left++;
}
// tmp = s1_set;
}
}
return false;
}
};
这个性能已经裂开了。。
此时我去看了看题解，发现使用集合这种思路可能不是一般人能想到的。
确实，记录s1中出现的所有字符，只需要使用一个 O(26) 大小的数组就可以了，为什么要逐个存在集合中呢？？
使用整数数组存字符频数，使得空间复杂度降低了许多。
对于滑动窗口，可以直接使窗口大小恒等于s1的长度，这样从左向右滑动就遍历完成所有可能符合条件 的子数组了。
每次滑动时，只有当前窗口左右边界的字符频数会发生变化，每次比较当前窗口的字符频数与s1数组的字符频数即可。
这样每次比较的时间复杂度为O(26)。
故有AC代码2。（就这种简单的思路还WA了两次）
AC代码2
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int len1 = s1.size();
int len2 = s2.size();
if (len1 > len2)
return false;
vector<int> cnt_diff(26, 0);
vector<int> cnt_s1(26, 0);
vector<int> cnt_s2(26, 0);
for (auto t : s1)
{
cnt_s1[t - 'a']++;
}
int left = 0;
int right = left + len1 - 1;
for (int i = left; i <= right; ++i)
{
cnt_s2[s2[i] - 'a']++;
}
if (cnt_s1 == cnt_s2) // 注意这里进行初始化后的第一次比对，WA过一次
return true;
while (right < s2.size() - 1) // 注意边界条件，防止++right溢出，这里WA过一次
{
char char_out = s2[left++];
char char_in = s2[++right];
if (char_out != char_in)
{
cnt_s2[char_out - 'a']--;
cnt_s2[char_in - 'a']++;
if (cnt_s1 == cnt_s2)
return true;
}
}
return false;
}
};
官方题解中还能进行优化：
Optimization 我没有实现此部分代码，官方题解见参考[1]。
小结本题，首先是把频数的匹配想的过于复杂了，之后是滑动窗口的构建不够灵性，这个题目能WA那么多次，恐怕昨天的状态也不是太好 o(╥﹏╥)o
参考资料
[1] 力扣官方题解.字符串的排列[EB/OL].2021-02-11