【力扣题解】【76. 最小覆盖子串】容易理解版

leetcode.cn/problems/minimum-window-substring/description/" rel="nofollow">76. 最小覆盖子串

总结和复盘

这是时隔1年4个月之后，再次写的题解，比第一次要清晰很多。
我刚开始，就是用方法一做的，提交之后报超出内存限制；
对方法一进行优化，得到方法二，提交之后就AC了。

这是第二次做这道题，
第一次的题解，是写给自己看的，有很多思考的过程，作为题解是不清晰的。
这一次的题解，会更好理解。

首先，我新增了两个成员函数，相当于把功能拆分开了，这样更容易我们去理解；
其次，由于使用了其他函数，于是我把过程之中用到的变量，提到了类中，做成了成员变量，这样我就方便在其他成员函数之中使用。

先做，再优化。

解法一

// 解法一 //
// 由于使用substr从s之中截取子字符串，并保存在answer之中，导致内存超出了限制class Solution {
public:string answer; // 这道题的答案（由于保存了结果字符串，导致内存超出了限制）unordered_map<char, int> window; // 这就是滑动的窗口unordered_map<char, int> need; // 目标字符串 t 中每个字符的情况int left = 0, right = 0; // 用于滑动的指针int validCount = 0; // 「与字符串t中数量相等的字符」的数量string minWindow(string s, string t) {// 初始化 needfor (char c : t)need[c]++;// 核心思想: 不断增大right找到一个可行解;while (right < s.length()) {char R = s[right];// 先看这第一步：R 是我们需要的字符时if (need.count(R) == 1) { window[R]++; // 要放到窗口之中if (window[R] == need[R]) { // 该字符的数量已经达到要求validCount++; // 已就绪的字符数量+1if (validCount == need.size()) { // 如果所有字符都就绪，更新一下answerupdateAnswer(s);}}}// 最后看这第三步// 你想啊，如果只是right++，left不动，那这个窗口岂不是越来越长了// 所以，要考虑一下什么时候left也要++// 核心思想：当前的窗口中，已经包含了不止一个解的时候，我们让left++，去优化一下// 因为题目要求找字符串s的最小字串// 比如：s="A-B-C---BAC--", t="ABC"// 不断的增加right指针，当这个窗口达到「A-B-C---BAC」时，// 这也是s的字串 且 也涵盖t中的所有字符// 但这不是最优解// 所以要增加left，让窗口变成「BAC」// 才是最优解moveLeftFindThePerfectAnswer(s, t);// 再看这第二步：R 不是我们需要的字符，则 right++ 继续寻找right++;}return answer;}void moveLeftFindThePerfectAnswer(const string& s, const string& t) {while (validCount == need.size()) { // 已经找到解的情况之下，才会优化解char L = s[left];if (need.count(L) == 1) { // 字符L是目标的其中一个字符时，代表可能可以优化updateAnswer(s);window[L]--;if (window[L] < need[L])validCount--;if (window[L] == 0)window.erase(L);}// 不管是否优化了，left都要增加。但至少要让窗口中保留一个有用的解，也就是while的条件left++;}}void updateAnswer(const string& s) {string tmp_answer = s.substr(left, right - left + 1);if (answer.empty()) { // 首次情况下answer = tmp_answer;} else if (tmp_answer.length() < answer.length()) { // 找到了更优化解的情况answer = tmp_answer;}}
};

解法二

// 解法二 //
// 优化answer的计算，不使用substr
// 因为答案是一个子串，是连续的，
// 所以使用start和len来保存即可，
// 到最后一刻，才使用substr从s之中截取子串出来class Solution {
public:struct MyAnswer {int start = INT_MAX;int len = INT_MAX;};MyAnswer answer; // 这道题的答案unordered_map<char, int> window; // 这就是滑动的窗口unordered_map<char, int> need; // 目标字符串 t 中每个字符的情况int left = 0, right = 0; // 用于滑动的指针int validCount = 0; // 「与字符串t中数量相等的字符」的数量string minWindow(string s, string t) {// 初始化 needfor (char c : t)need[c]++;// 核心思想: 不断增大right找到一个可行解;while (right < s.length()) {char R = s[right];// 先看这第一步：R 是我们需要的字符时if (need.count(R) == 1) { window[R]++; // 放到窗口之中if (window[R] == need[R]) { // 该字符的数量已经达到要求validCount++; // 已就绪的字符数量+1if (validCount == need.size()) { // 如果所有字符都就绪，更新一下answerupdateAnswer(s);}}}// 最后看这第三步// 你想啊，如果只是right++，left不动，那这个窗口岂不是越来越长了// 所以，要考虑一下什么时候left也要++// 核心思想：当前的窗口中，已经包含了不止一个解的时候，我们让left++，去优化一下// 因为题目要求找字符串s的最小字串// 比如：s="A-B-C---BAC--", t="ABC"// 不断的增加right指针，当这个窗口达到「A-B-C---BAC」时，// 这也是s的字串 且 也涵盖t中的所有字符// 但这不是最优解// 所以要增加left，让窗口变成「BAC」// 才是最优解moveLeftFindThePerfectAnswer(s, t);// 再看这第二步：R 不是我们需要的字符，则 right++ 继续寻找right++;}// 要考虑没有找到解的情况，返回空字符串return (answer.start == INT_MAX && answer.len == INT_MAX)? "" : s.substr(answer.start, answer.len);}void moveLeftFindThePerfectAnswer(const string& s, const string& t) {while (validCount == need.size()) { // 已经找到解的情况之下，才会优化解char L = s[left];if (need.count(L) == 1) { // 字符L是目标的其中一个字符时，代表可能可以优化updateAnswer(s);window[L]--;if (window[L] < need[L])validCount--;if (window[L] == 0)window.erase(L);}// 不管是否优化了，left都要增加。但至少要让窗口中保留一个有用的解，也就是while的条件left++;}}void updateAnswer(const string& s) {int new_length = right - left + 1;if (answer.start == INT_MAX && answer.len == INT_MAX) { // 首次情况下answer.start = left;answer.len = new_length;} else if (new_length < answer.len) { // 找到了更优化解的情况answer.start = left;answer.len = new_length;}}
};