Description:
Given a string source and a string target, find the minimum window in source which will contain all the characters in target.
Example
source = "ADOBECODEBANC" target = "ABC" Minimum window is "BANC".
Challenge
Can you do it in time complexity O(n) ?
Clarification
Should the characters in minimum window has the same order in target?
- Not necessary.
Solution:
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) {
auto l1 = (int)source.length();
auto l2 = (int)target.length();
if (l2 == 0 || l1 < l2) return "";
int require[256] = {0};
bool exists[256] = {false};
int count = l2;
for (int i = 0; i < l2; ++i) {
++require[target[i]];
exists[target[i]] = true;
}
int minLen = INT_MAX, minL = -1;
int left = 0, right = 0;
while (right <= l1) {
if (count > 0) {
if (right == l1) break;
if (require[source[right]] > 0) --count;
if (exists[source[right]]) --require[source[right]];
++right;
} else {
if (right-left < minLen) {
minLen = right-left;
minL = left;
}
if (exists[source[left]]) ++require[source[left]];
if (require[source[left]] > 0) ++count;
++left;
}
}
return minLen > l1 ? "" : source.substr(minL, minLen);
}
};
转载于:https://www.cnblogs.com/deofly/p/minimum-window-substring.html
