567 字符串的排列
看到子串想到滑动窗口,套用框架,接着只需要想清楚以下几个问题:
- 如何判断s2包含s1的排列
- 什么时候需要收缩滑动窗口
- 什么时候返回结果
问题1:
s2包含s1的排列 => s1的字符s2都有 => 使用哈希表need统计s1的字符个数,使用哈希表window统计s2的字符个数,比较need和window的字符个数是否对应。思路与76 最小覆盖子串相同
问题2:
从用例可以看出,s2不仅拥有s1的字符个数,而且「排列」使得s1排列后的字符是连续的,s2不能像76 最小覆盖子串只包含字符,还要让这些字符连续排列,为此我们维护一个和s1长度大小相同的窗口即可
因此s2的长度必须大于等于s1,当s2长度大于等于s1时收缩窗口,直到s2长度小于s1停止
问题3:
与76 最小覆盖子串不同,76 最小覆盖子串如果发现字符个数match还会继续收缩,直到子串最小;本题如果发现s2包含s1排列,立即返回结果,因此返回条件就是valid == need.size(),对应地,该条件是76 最小覆盖子串的收缩条件。
class Solution {
public:
bool checkInclusion(string s1, string s2) {
// window只记录need对应字符的个数
unordered_map<char, int> window, need;
for(char c : s1){
need[c]++;
}
int left = 0, right = 0;
int valid = 0;
while(right < s2.size()){
char c = s2[right];
right++;
if(need.count(c)){
window[c]++;
if(window[c] == need[c]){
valid++;
}
}
// 这里是>= 因为窗口为[left, right) 长度为right - left
// 窗口长度不能小于s1,但是可以等于,甚至等于的时候是最优解
while(right - left >= s1.size()){
// valid和need比较,而不是s1
if(valid == need.size())
return true;
char d = s2[left];
left++;
if(need.count(d)){
if(window[d] == need[d]){
valid--;
}
window[d]--;
}
}
}
return false;
}
};
由于判断的是s2是否包含s1的排列,我们只需要维护一个定长为s1.size()的窗口,判断这个窗口字符个数与s1是否相同,因此while可以改为if(while和if的效果一样,这时因为收缩条件是长度)
class Solution {
public:
bool checkInclusion(string s1, string s2) {
unordered_map<char, int> window, need;
for(char c : s1){
need[c]++;
}
int left = 0, right = 0;
int valid = 0;
while(right < s2.size()){
char c = s2[right];
right++;
if(need.count(c)){
window[c]++;
if(window[c] == need[c]){
valid++;
}
}
// 这里优化,把while改为了if
if(right - left >= s1.size()){
if(valid == need.size())
return true;
char d = s2[left];
left++;
if(need.count(d)){
if(window[d] == need[d]){
valid--;
}
window[d]--;
}
}
}
return false;
}
};