ZBLOG

滑动窗口解决最小覆盖字串问题,请给出一个c++版本小demo,并且施加注释

#include <iostream>
#include <unordered_map>
using namespace std;

string minWindow(string s, string t) {
    unordered_map<char, int> need, window;  // 分别记录需要的字符和窗口中的字符
    for (char c : t) need[c]++;             // 统计需要的字符

    int left = 0, right = 0;                // 左右指针
    int valid = 0;                          // 记录窗口中满足need条件的字符个数
    int start = 0, len = INT_MAX;           // 记录最小覆盖子串的起始位置和长度

    while (right < s.size()) {              // 移动右指针
        char c = s[right];
        right++;                            // 右移窗口
        if (need.count(c)) {                // 如果该字符是需要的
            window[c]++;                    // 放入窗口
            if (window[c] == need[c])        // 如果已经满足need条件
                valid++;                    // valid加1
        }

        while (valid == need.size()) {       // 如果窗口中包含了所有需要的字符
            if (right - left < len) {        // 更新最小覆盖子串的位置和长度
                start = left;
                len = right - left;
            }
            char d = s[left];               // 左指针向右移动
            left++;
            if (need.count(d)) {            // 如果该字符是需要的
                if (window[d] == need[d])    // 如果窗口中该字符数量已经等于need中数量
                    valid--;                // valid减1
                window[d]--;                // 从窗口中移除该字符
            }
        }
    }

    return len == INT_MAX ? "" : s.substr(start, len);   // 返回最小覆盖子串
}

int main() {
    string s = "ADOBECODEBANC";
    string t = "ABC";
    cout << minWindow(s, t) << endl;    // 输出:BANC
    return 0;
}

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://sdn.0voice.com/?id=168

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?