leetcode:最小覆盖字符串

1笨方法对于算法题目自己能想到的往往是最基础的笨方法。代码如下如果t的长度是len1s的长度是len2那么最小窗口是len1最大窗口是len2。所以可以从len1到len2遍历窗口大小对于每个窗口大小将窗口从前向后进行移动。因为窗口是从小到大进行遍历所以第一次遇到满足条件的子串时就可以直接返回。这种算法的时间复杂度是O(n*n)在leetcode上运行会超时。class Solution { public: string minWindow(string s, string t) { std::mapchar, int tConstMap; std::mapchar, 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::mapchar, int tConstMap; std::mapchar, 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 ; };