reLeetCode 热题 100- 76 最小覆盖串

 

自己 滑动窗

 

class Solution {
public:
// 自己第一个 5% 时间满 内存64% 动态滑动窗string minWindow1(string s, string t) {if(s.size()<t.size()){return "";}vector<int> t_v;unordered_map<char,int> t_map;for(int i=0;i<t.size();i++){//t_map[t[i]-'a']++;t_map[t[i]]++;}unordered_map<char,int> c_map;int left=-1;int right=0;int min_=s.size();int left_taget=-1;int right_taget=-1;string result_="";for(int i=0;i<s.size();i++){right=i;if(t_map.contains(s[i])){if(left==-1)left=i;}else{continue; }c_map[s[i]]++;bool ok_=1;for(auto &pair:t_map){    if(c_map[pair.first]<t_map[pair.first]){   ok_=0;break;}}if(ok_){if(right-left+1<=min_){left_taget=left;right_taget=right;min_=right-left+1;}c_map[s[left]]--;left++; while(left<=right && left<s.size()){// cout<< " left" <<left<<endl;if(c_map.contains(s[left])){  c_map[s[i]]--;--i;break;}left++; }// c_map[s[i]]--;// --i;} }if(left_taget>=0 && right_taget>=0){   if(left_taget==right_taget){result_=s[left_taget];}else{result_=s.substr(left_taget,right_taget-left_taget+1); //1子字符串的起始位置（索引） 2要提取的子字符串长度}}return result_;}string minWindow(string s, string t) {string result_；vector<int> t_v(26);for(int i=0;i<t.size();i++){t_v[t[i]-'a']++;}vector<int> current_v;map<vector<int>,int> all_map;for(int right=0;right<s.size();right++){current_v[s[right]-'a']++;all_map[current_v]++;}for(int right=0;right<s.size();right++){all_map}return result_;}
};