壮年听雨客舟中
江阔云低
断雁叫西风
暴力代码：
class Solution {
public:
string minWindow(string s, string t) {
auto *hash = new int[128], *thash = new int[128];
memset(hash, 0, 128 * sizeof(int));
for (const char it : t) hash[it]++;
int count = t.length();
int left = -1, len = INT32_MAX;
for (int i = count - 1; i < s.length(); i++) {
if (hash[s[i]]) {
int cnt = count, j = i;
memcpy(thash, hash, 128 * sizeof(int));
for (; j >= 0; j--) {
if (thash[s[j]]) {
cnt--;
thash[s[j]]--;
}
if (cnt == 0) break;
}
if (cnt == 0) {
if (i - j + 1 < len) {
len = i - j + 1;
left = j;
}
}
}
}
delete[] hash;
delete[] thash;
if (left >= 0)
return s.substr(static_cast<size_t>(left), static_cast<size_t>(len));
else
return std::string();
}
};
然后通过维护两个hash之间的关系来寻找最小的满足长度。
两个hash的关系：对于所有的0 <= i < len，要满足thash[i] >= hash[i]，然后在移动left和right，right往后移动则会让thash保持变大，left往右移动会让thash变小。
class Solution {
public:
string minWindow(string s, string t) {
auto *hash = new int[128], *thash = new int[128];
memset(hash, 0, 128 * sizeof(int));
for (const char it : t) hash[it]++;
size_t cnt = t.length();
size_t left = 0, right = 0, len = 0, start = 0;
memcpy(thash, hash, 128 * sizeof(int));
for (size_t i = 0; i < s.length(); i++) {
if (thash[s[i]]) {
cnt--;
thash[s[i]]--;
}
if (cnt == 0) {
right = i;
len = right - left + 1;
start = left;
break;
}
}
if (right != 0) {
memset(thash, 0, 128 * sizeof(int));
for (int i = 0; i <= right; i++)
if (hash[s[i]]) thash[s[i]]++;
while (right < s.length()) {
char itleft = s[left];
if (hash[itleft] == 0 || thash[itleft] > hash[itleft]) {
if (thash[itleft] > hash[itleft]) thash[itleft]--;
left++;
if (right - left + 1 < len || len == 0) {
start = left;
len = right - left + 1;
}
} else {
right++;
if (right < s.length()) {
char itright = s[right];
if (hash[itright])
thash[itright]++;
}
}
}
}
delete[] hash;
delete[] thash;
if (len)
return s.substr(start, len);
else
return std::string();
}
};
