BM90. 最小覆盖子串
描述
找出的最短子串为.
注意：
如果 s 中没有包含 t 中所有字符的子串，返回空字符串 “”；
满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。
示例1
输入:
"XDOYEZODEYXNZ","XYZ"
输出:
"YXNZ"
示例2
输入:
"abcAbA","AA"
输出:
"AbA"
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-07-24
class Solution {
public:
bool cheak(unordered_map<char, int>& umap) {//检查hash中是否全部>0
for (auto iter = umap.begin(); iter != umap.end(); iter++) {
if (iter->second < 0) {
return false;
}
}
return true;
}
string minWindow(string S, string T) {//O(N) O(N)
if (S.size() == 0) {
return "";
}
string str = "";
//yw
int res = INT_MAX;
unordered_map<char, int> umap;//初始化umap
for (int i = 0; i < T.size(); i++) {
umap[T[i]] -= 1;
}
int start = -1;
for (int i = 0, j = i; i < S.size() && j < S.size(); ) {
// if (!cheak(umap)) {
if (umap.count(S[j])) { //匹配到+1；
umap[S[j]]++;
}
j++;
// } else {
while (cheak(umap)) {//检查
if (res > j - i) { //更新窗口
res = j - i;
start = i;
}
if (umap.count(S[i])) { //更新hash
umap[S[i]]--;
}
i++;//缩小窗口
}
// }
}
if (start == -1) {//左窗口没动，说明左没右移，返回空串
return "";
}
str = S.substr(start, res);
//fanhui
return str;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-07-20
class Solution {
public:
/**
*
* @param S string字符串
* @param T string字符串
* @return string字符串
*/
string minWindow(string S, string T) {
// write code here
if (S.size() < T.size()) {
return "";
}
unordered_map<char, int> ump_s, ump_t;
for (char ch : T) {
++ump_t[ch];
}
int start = 0, len = INT_MAX;
int cnt = 0;
int left = 0, right = 0;
while (right < S.size()) {
++ump_s[S[right]];
if (ump_s[S[right]] <= ump_t[S[right]]) {
++cnt;
}
while (ump_s[S[left]] > ump_t[S[left]]) {
--ump_s[S[left]];
++left;
}
if (cnt == T.size() && len > right - left + 1) {
len = right - left + 1;
start = left;
}
++right;
}
return len == INT_MAX ? "" : S.substr(start, len);
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-05-22
class Solution {
public:
/**
*
* @param S string字符串
* @param T string字符串
* @return string字符串
*/
string minWindow(string S, string T) {
// write code here
string res;
if(T.size()==0||S.size()==0) return res;
int minl=-1;
int minr=S.size();
int count=0;
map<char,int> dq;
for(auto c:T){
dq[c]--;
count++;
}
int left=0;
for(int i=0;i<S.size();i++){
if(dq.find(S[i])!=dq.end()){
dq[S[i]]++;
if(dq[S[i]]<=0)
count--;
if(count==0){
while(dq.find(S[left])==dq.end()||dq[S[left]]>0){
if(dq.find(S[left])!=dq.end()) dq[S[left]]--;
left++;
}
if((i-left)<(minr-minl)){
minr=i;
minl=left;
dq[S[left]]--;
count++;
left++;
}
}
}
}
for(int i=minl;i<=minr;i++){
res+=S[i];
}
return res;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-04-14
class Solution {
public:
/**
*
* @param S string字符串
* @param T string字符串
* @return string字符串
*/
//检查hash表是否都是0
bool checkZ(unordered_map<char, int>& hash)
{
for(auto iter = hash.begin(); iter != hash.end(); ++iter)
{
if(iter->second < 0) return false;
}
return true;
}
string minWindow(string S, string T) {
int cnt = S.length() + 1;
unordered_map<char, int> hash;
//初始化哈希
for(int i = 0; i < T.length(); ++i)
{
hash[T[i]] -= 1;
}
//快慢指针和维护一个窗口
int slow = 0;
int fast = 0;
int left = -1;
int right = -1;
for(; fast < S.length(); ++fast)
{
char c = S[fast];
if(hash.count(c)) hash[c]++;
while(checkZ(hash))
{
if(cnt > fast - slow + 1)
{
cnt = fast - slow + 1;
left = slow;
right = fast;
}
char f = S[slow];
//缩小窗口的时候减一
if(hash.count(f)) hash[f]--;
//缩小窗口
slow++;
}
}
//没找到
if(left == -1) return "";
else return string(S.begin() + left, S.begin() + right + 1);
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 400KB, 提交时间: 2022-05-13
class Solution {
public:
//关键：T中还可能包含重复的字符，如 'XXYYZ' 'aa'，因次哈希表初始记录T中出现的次数（复数）
//滑动窗口
bool check(unordered_map<char,int>& hash){
for(auto i = hash.begin();i!=hash.end();i++){
if((*i).second<0)
return false;
}
return true;
}
string minWindow(string S, string T) {
unordered_map<char,int>m;
//初始化哈希表（都为复数，找到就+1）
for(int i = 0;i<T.size();i++){
m[T[i]]-=1; //如果有就计算，没有就添加
}
int slow = 0,fast = 0;
int left = -1,right = -1;
int cnt = S.size()+1;
for(;fast<S.size();fast++){
char c = S[fast];
if(m.count(c)){
m[c]++;
}
while(check(m)){
if(cnt>fast-slow+1){
cnt = fast-slow+1;
left = slow;
right = fast;
}
char c = S[slow];
if(m.count(c)){
m[c]--;
}
slow++;
}
}
//找不到
if(left==-1)
return "";
return string(S.begin()+left,S.begin()+(right+1));
}
};