移动窗口类型
发现这道题居然没有归类
就是
32. Minimum Window Substring
647. Find All Anagrams in a String
386. Longest Substring with At Most K Distinct Characters
就是
32. Minimum Window Substring
647. Find All Anagrams in a String
386. Longest Substring with At Most K Distinct Characters
这也是一大类。
缘起：
给两个string，一个source，一个target，在source中找包含target 的最短的subtring。这是典型移动窗口类。在array或string中移动一个窗口，每次移动要更新窗口的结果。
数据结构：
借助hash或是vector 去找到每个元素出现次数。窗口移动时，旧的元素次数减一，新的次数加一。
32这个题有些弯弯绕，但理清思路很有意思。用hashmapping 次数是0还是>0, 来变达source里面是否出现了target里面的元素。
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
string res = "";
const int ss = source.size();
const int st = target.size();
if(ss < st){
return res;
}
unordered_map<char, int> hMp;
for(char c : target){
hMp[c]++;
}
int cnt = 0;
int left = 0;
int minLen = INT_MAX;
int start = 0;
for(int i = 0; i < source.size(); i++){
if(--hMp[source[i]] >= 0){
cnt++;
}
if(cnt == st){
while(cnt == st){
if(++hMp[source[left]] > 0){
cnt--;
}
left++;
}
if(minLen > i - (left - 1) + 1){
minLen = i - left + 2;
start = left - 1;
}
}
}
return minLen == INT_MAX ? "" : source.substr(start, minLen);
}
};
Comments
Post a Comment