From index 0 to size-1, start = 0; end = 0; end move until 满足条件,然后记得把start在hash里清掉,继续移动start.
class Solution {
public:
/*
* @param source : A string
* @param target: A string
* @return: A string denote the minimum window, return "" if there is no such a string
*/
string minWindow(string &source , string &target) {
// write your code here
vector<int> hashS (256, 0);
vector<int> hashT (256, 0);
int start = 0;
int end = 0;
int minLength = INT_MAX;
string result = "";
//if (source.size() < target.size()) {
// return "";
//}
if (source == "" && target == "") {
return "";
}
for (int i = 0; i < target.length(); i++) {
hashT[target[i]]++;
}
for (;start < source.length(); start++) {
while (end < source.length() && !isValid(hashS, hashT)) {
hashS[source[end]]++;
end++;
}
if (isValid(hashS, hashT)) {
if (end - start < minLength) {
result = source.substr(start, end - start);
minLength = end - start;
}
}
if (hashS[source[start]] > 1) {
hashS[source[start]]--;
} else {
hashS[source[start]] = 0;
}
}
return result;
}
bool isValid(vector<int> &hashS, vector<int> &hashT) {
for (int i = 0; i < 256; i++) {
if (hashS[i] < hashT[i]) {
return false;
}
}
return true;
}
};