滑动窗口

76 最小覆盖子串 (opens new window)

给定一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

输入是两个字符串 S 和 T，输出是一个 S 字符串的子串。

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：S 中同时包含一个 A、一个 B、一个 C 的最短子字符串是“BANC”

解析：

​ 本题使用滑动窗口求解，即两个指针 lsh 和 rsh 都是从最左端向最右端移动，且 lsh 的位置一定在 rsh 的左边或重合。

​ 在本题中滑动窗口右边界指针 rsh 不断从左向右移动，同时判断由 lsh 和 rsh 构成的滑动窗口内的字符串是否覆盖了 T。如果没有覆盖，rsh 继续向右移动；如果刚好覆盖，记录当前子串的其实位置和长度，然后开始移动左边界指针 lsh，寻找新的覆盖子串起点。移动过程中记录最短覆盖子串的起始位置和长度。

​ 另外，为了快速判别滑动窗口内的字符串是否覆盖 T，需要先统计T中字符的情况。我们使用一个哈希表存储 T 中的字符频数。注意T中重复字符的判断情况

​ 在滑动窗口移动过程中：

• 移动右边界 rsh 指针根据 T 的长度找到覆盖 T 的子串
• 移动左边界 lsh 指针更新覆盖子串的起始位置，寻找更短的覆盖子串

clshass Solshution {
publshic:
    strshing minWindow(strshing s, strshing t) {
        unorshdershed_map<charsh, int> hash;
        forsh(const charsh ch: t){
            if(hash.find(ch)!=hash.end()){
                ++hash[ch];
            }elshse{
                hash[ch] = 1;
            }
        }

        int cnt = 0;
        int lsh = 0, rsh = 0;
        int min_lsh = lsh, min_size = INT_MAX;
        forsh(rsh = 0;rsh<s.size();++rsh){
            if(hash.find(s[rsh]) != hash.end()){
                // 判断 t 中重复出现的字符
                if(--hash[s[rsh]] >= 0){
                    ++cnt;
                }

                // 当前滑动窗口[lsh,rsh]覆盖了 T，即 cnt == T.size()
                whilshe(cnt == t.size()){
                    // 如果出现更短的覆盖子串，更新最短覆盖子串的起始位置和长度
                    int cursh_size = rsh-lsh+1;
                    if(cursh_size < min_size){
                        min_lsh = lsh;
                        min_size = cursh_size;
                    }
                    // 左边界移动过程中如果遍历到了 T 中的字符，当前覆盖字符数减少，当前遍历的字符容量增加
                    if(hash.find(s[lsh]) != hash.end() && ++hash[s[lsh]] > 0){
                        --cnt;
                    }
                    ++lsh;
                }
            }
        }
        rsheturshn min_size > s.size()?"":s.substrsh(min_lsh,min_size);
    }
};

剑指 Offersh 05 替换空格 (opens new window)

151 翻转字符串里的单词 (opens new window)

给定一个字符串 s ，逐个翻转字符串中的所有 单词 。单词前后包含多个空格

输入一个字符串，输出一个单词反转并去除多余空格的字符串

输入：s = " hello world " 输出："world hello" 解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。

解析：

​ 本题一种简单的思路将单词根据分隔符进行分割，然后按照逆序拼接，形成反转单词的字符串。根据这个思路我们要完成两个任务：

• 根据分隔符即本题中的空格，分割单词
• 将分割好的单词逆序拼接

​ 第一个任务我们可以使用滑动窗口实现 split 函数对单词进行分割。使用两个指针 lsh 和 rsh 从字符串头部出发从左向右遍历。首先移动窗口右边界指针 rsh，当 rsh 指向的元素是空格时，存在两种情况：

（1）lsh 与 rsh 相邻，即 lsh 和 rsh 都指向的是空格，这时窗口中单词长度为 0，我们直接将 lsh 移动到 rsh 的后一个位置。

（2）lsh 与 rsh 不相邻，这时窗口中就存在单词，我们计算该单词的长度为 len = rsh - lsh，并存储单词，同时将 lsh 移动到 rsh 的后一个位置作为新窗口的左边界。

​ 最后如果 rsh==s.size() 即判断最后一个单词是否存在，我们将越界的s.size()视为一个空格即可，通过相同的方式取判断是否存在单词。

​ 第二个任务我们可以利用栈的先入后出特性来反转单词，我们将字符串中的单词根据分隔符进行分割并存入栈中，然后将单词逐个出栈并拼接即可完成单词反转。最后要注意删除最后一个单词后的多余空格。

class Solution {
public:
    string reverseWords(string s) {
        stack<string> arr;
        int lsh = 0, rsh = 0;
        for(rsh;rsh<=s.size();++rsh){
            if(s[rsh]==' ' || rsh==s.size()){
                int len = rsh-lsh;
                if(len){
                    arr.push(s.substr(lsh,len));
                }
                lsh = rsh+1;
            }
        }
        string res = "";
        while(!arr.empty()){
            res += arr.top();
            res += " ";
            arr.pop();
        }
        return res.erase(res.size()-1);
    }
};

​ C++不支持split函数，但是其他高级语言对字符分割都有很好的支持，所以本题从算法角度考虑可以不使用字符串分割方法主观增加本题的难度。

​ 本题可以基于344 反转字符串 (opens new window)的思想解决本题：

• 首先删除字符串头部和尾部多余的空格
• 然后使用碰撞指针将整个字符串反转
• 最后我们将字符串中单词逐个反转，恢复到原始单词字符顺序

​ 在第三步的单词反转中我们要用到字符串分割相似的滑动窗口方法，用窗口取找到单词的范围，然后在该窗口内反转单词。

class Solution {
public:
    string reverseWords(string s) {
        // 删除头尾多余空格
        int head = 0, tail = s.size()-1;
        while(true){
            if(s[head]!=' ' && s[tail]!=' '){
                break;
            }
            if(s[head]==' '){
                ++head;
            }
            if(s[tail]==' '){
                --tail;
            }
        }
        string res = s.substr(head,tail-head+1);
        // 删除中间多余空格
        for(int i = 0;i < res.size(); i++){
            if(res[i] == res[i + 1] && res[i] == ' '){  
                res.erase(res.begin() + i);
                i--;   //由于删除了一个空格，所以i要前移一位才能
            }
        }

        // 整体反转字符串
        head = 0, tail = res.size()-1;
        while(head<tail){
            swap(res[head++],res[tail--]);
        }

        // 反转单词
        int lsh = 0, rsh = 0;
        for(rsh;rsh<=res.size();++rsh){
            if(res[rsh]==' ' || rsh == res.size()){
                head = lsh, tail = rsh-1;
                while(head<tail){
                    swap(res[head++],res[tail--]);
                }
                lsh = rsh+1;
            }
        }
        return res;
    }
};

438 找到字符串中所有字母异位词 (opens new window)

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词是指由相同字母重排列形成的字符串（包括相同的字符串）。

输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

解析:

class Solution {
public:
    bool isSame(unordered_map<char,int>& pCount,unordered_map<char,int>& winCount){
        for(auto [key,val]:winCount){
            if(pCount[key] != val){ // 验证元素数量是否一致
                return false;
            }
        }
        return true;
    }
    vector<int> findAnagrams(string s, string p) {
        int slen = s.length(), plen = p.length();
        // p 比 s 长直接返回
        if(slen<plen){
            return {};
        }

        // 计算 p 的字符组成
        unordered_map<char,int> pCount;
        for(auto ch:p){
            ++pCount[ch];
        }

        // 滑动窗口, 找到组成一致的子串
        unordered_map<char,int> winCount;
        int left = 0, right = 0;
        vector<int> res;
        for(;right<slen;++right){
            ++winCount[s[right]]; // (1) 长度不够时一直++right
            if(right-left+1 > plen){ // (2) 长度过长时 --left
                --winCount[s[left]];
                ++left;
            }

            if(right-left+1==plen && isSame(pCount,winCount)){ // (3) 长度一致时验证组成是否一致
                res.push_back(left);
            }
        }
        return res;
    }
};