這個解法跟 #567 和 #438 是一脈相承,主要的差異是在於將 wineowStart 往前移動的條件不一樣,這邊的條件是,只要目前的 window 還包含 pattern 裡的所有字母,就應該要縮減 windowStart,並且在移動過程、得到更小的 substring 時,要更新 res。實作如下:
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> table;
for(auto c:t)
table[c]++;
string res = s;
res += s;
int windowStart = 0, matched = 0;
for(int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
char endChar = s[windowEnd];
if(table.find(endChar) != table.end()) {
table[endChar]--;
if(table[endChar] == 0) {
matched++;
}
}
while(matched == table.size()) {
if(windowEnd - windowStart + 1 < res.length()) {
res = s.substr(windowStart, windowEnd - windowStart + 1);
}
char startChar = s[windowStart++];
if(table.find(startChar) != table.end()) {
if(table[startChar] == 0)
matched--;
table[startChar]++;
}
}
}
return res.length() == s.length()*2 ? "" : res;
}
};