leetcode:最小覆盖字符串
1笨方法
对于算法题目，自己能想到的往往是最基础的笨方法。
代码如下：
如果t的长度是len1，s的长度是len2，那么最小窗口是len1，最大窗口是len2。所以可以从len1到len2，遍历窗口大小，对于每个窗口大小，将窗口从前向后进行移动。因为窗口是从小到大进行遍历，所以第一次遇到满足条件的子串时，就可以直接返回。这种算法的时间复杂度是O(n*n)，在leetcode上运行会超时。
class Solution { public: string minWindow(string s, string t) { std::map<char, int> tConstMap; std::map<char, int> tTmpMap; for (char c : t) { if (tConstMap.count(c) > 0) { tConstMap[c]++; } else { tConstMap[c] = 1; } tTmpMap[c] = 0; } int minWindow = t.size(); int maxWindow = s.size(); int maxLength = s.size(); for (int window = minWindow; window <= maxWindow; window++) { for (int i = 0; i <= maxLength - window; i++) { for (int j = i; j < i + window; j++) { if (tConstMap.count(s[j]) > 0) { tTmpMap[s[j]]++; } } bool result = true; for (auto [c, count] : tTmpMap) { if(count < tConstMap[c]) { result = false; } tTmpMap[c] = 0; } if (result == true) { std::cout << "i:" << i <<",window:" << window <<std::endl; return s.substr(i, window); } } } return ""; } };针对上边的代码，我们可以看到，针对一个确定大小的window，在从前向后遍历的过程中，每次只移动了一个字符的位置，但是每次都要对tTmpMap进行清空并重新计算，完全可以只对移出窗口的元素和移入窗口的元素进行处理。但是时间复杂度仍然较高，在leetcode上运行会超时。
class Solution { public: string minWindow(string s, string t) { std::map<char, int> tConstMap; std::map<char, int> tTmpMap; for (char c : t) { if (tConstMap.count(c) > 0) { tConstMap[c]++; } else { tConstMap[c] = 1; } tTmpMap[c] = 0; } int minWindow = t.size(); int maxWindow = s.size(); int maxLength = s.size(); for (int window = minWindow; window <= maxWindow; window++) { for (int i = 0; i <= maxLength - window; i++) { if (i == 0) { for (auto [c, value] : tTmpMap) { tTmpMap[c] = 0; } for (int j = i; j < i + window; j++) { if (tConstMap.count(s[j]) > 0) { tTmpMap[s[j]]++; } } } else { if (tConstMap.count(s[i +window - 1]) > 0) { tTmpMap[s[i +window - 1]]++; } } bool result = true; for (auto [c, count] : tTmpMap) { if(count < tConstMap[c]) { result = false; break; } } if (result == true) { return s.substr(i, window); } if (tTmpMap.count(s[i]) > 0) { tTmpMap[s[i]]--; } } } return ""; } };2leetcode题解一
官方题解中没有遍历窗口的大小，而是使用双指针的方式。用窗口的左边沿和右边沿来表示一个窗口，通过左右边沿的移动来遍历不同的情况。
class Solution { public: //t中字符出现的次数 unordered_map <char, int> ori; //s中字符出现的次数 unordered_map <char, int> cnt; //判断当前子串是不是覆盖了t bool check() { for (const auto &p: ori) { if (cnt[p.first] < p.second) { return false; } } return true; } string minWindow(string s, string t) { //t中字符出现的次数 for (const auto &c: t) { ori[c]++; } int l = 0;//窗口左边沿 int r = 0;//窗口右边沿 int len = INT_MAX; int ansL = -1; int ansR = -1; while (r < int(s.size())) { //统计s中字符的数量，移动窗口右边沿 if (ori.find(s[r]) != ori.end()) { cnt[s[r]]++; } //移动窗口左边沿，找到慢去条件的最小窗口 while (check() && l <= r) { if (r - l + 1 < len) { len = r - l + 1; ansL = l; } if (ori.find(s[l]) != ori.end()) { cnt[s[l]]--; } l++; } r++; } return ansL == -1 ? string() : s.substr(ansL, len); } };3leetcode题解二
题解二比题解一性能更高。
相同点：
①都维护了两个map，分别用于记录s和t中字符出现的次数。
②窗口右边沿的移动均是沿着s进行移动，没有其它的条件约束。
不同点：
①题解二中多了一个count，用count和t的长度是否相等来表示当前子串是不是覆盖了t。当s中的字符出现次数少于t中字符的出现次数时，对count进行递增。而题解一种使用函数check来判断当前子串是不是覆盖了t。
②窗口左边沿的移动方式不同：题解一种移动左边沿，加上check函数进行判断，比较好理解；题解二中移动左边界，是当当前字符出现的次数比t中出现的次数多的时候，才会像猴移动(如果字符在t中没有出现，在s中出现了，那么会移动；如果字符在s和t中都出现了，并且在s中出现的次数比t中多，那么也可以移动)。
class Solution { public: string minWindow(string s, string t) { for (char c : t) { ht[c]++; } for (int i = 0, j = 0; i < s.size(); i++) { hs[s[i]]++; if (hs[s[i]] <= ht[s[i]]) { count++; } while (hs[s[j]] > ht[s[j]]) { hs[s[j]]--; j++; } if (count == t.size()) { if (ret.empty() || i - j + 1 < ret.size()) { ret = s.substr(j, i - j + 1); } } } return ret; } private: int hs[123] = {0}; int ht[123] = {0}; int count = 0; std::string ret = ""; };