leetcode-76-最小覆盖子串
//时间空间占用都比较大
//感觉写的比较乱
class Solution {
public:
bool helper(vector<int> &freq_s, vector<int> &freq_t, string t) {
for (int i = 0; i<t.length(); i++) {
if (freq_s[t[i]] < freq_t[t[i]]) return false;
}
return true;
}
string minWindow(string s, string t) {
string res = "";
if (s.length()<t.length()) return res;
int N = s.length(), n = t.length(), left = 0, right = left + n - 1;
vector<int> freq_s(256, 0), freq_t(256, 0);
for (int i = 0; i<n; i++) {
freq_s[s[i]]++;
freq_t[t[i]]++;
}
while (!helper(freq_s, freq_t, t)) {//还不满足
if (right == N - 1) return res;
freq_s[s[++right]]++; //右指针向右,直到满足条件
}
res = s.substr(left, (right - left + 1));
if (res.length() == n) return res;
while (left < N - n && right <N) {
if (helper(freq_s, freq_t, t)) {
while (helper(freq_s, freq_t, t)) {
res = ((right - left + 1)<res.length()) ? s.substr(left, (right - left + 1)) : res;
freq_s[s[left++]]--;
}
}
else freq_s[s[left++]]--;
freq_s[s[++right]]++;
}
return res;
}
};
int main()
{
Solution sol;
string s = "aaaaaaaaaaaabbbbbcdd", p = "abcdd";
cout << sol.minWindow(s, p);
cout<< endl;
return 0;
}