跳转至

567 字符串的排列

看到子串想到滑动窗口,套用框架,接着只需要想清楚以下几个问题:

  1. 如何判断s2包含s1的排列
  2. 什么时候需要收缩滑动窗口
  3. 什么时候返回结果

问题1:

s2包含s1的排列 => s1的字符s2都有 => 使用哈希表need统计s1的字符个数,使用哈希表window统计s2的字符个数,比较need和window的字符个数是否对应。思路与76 最小覆盖子串相同

if(need.count(c)){
    window[c]++;
    if(window[c] == need[c])
        valid++;
}

问题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;
    }
};