lintcode(12)——最小子串覆盖的解题思路和代码实现

32. 最小子串覆盖

给定一个字符串source和一个目标字符串target，在字符串source中找到包括所有目标字符串字母的最短子串。

样例

例1:

输入:
""
""
输出:
""


例2:

输入:
"ADOBECODEBANC"
"ABC"
输出:
"BANC"


挑战

要求时间复杂度为O(n)

说明

在答案的子串中的字母在目标字符串中是否需要具有相同的顺序？——不需要。

注意事项

如果在source中没有这样的子串，返回""。

如果有多个这样的子串，保证在source中始终只有一个唯一的最短子串。

目标字符串可能包含重复字符，最小窗口应覆盖所有字符，包括目标中的重复字符

class Solution {
public:
string minWindow(string &s , string &t) {
// write your code here
unordered_map mp;
for (char now : t)
{
mp[now] ++;
}
int count = mp.size();
int j = 0;
int ans = INT_MAX;
string res;
for (int i = 0; i while(count > 0 && j mp[s[j]]--;
if (mp[s[j]] == 0) {
count--;
}
j++;
}
if (count == 0 && j - i ans = j - i;
res = s.substr(i, j - i); //截取字符串，从指定位置开始截取指定长度的字符串
}
if(mp[s[i]] == 0) {
count++;
}
mp[s[i]]++;
}
return res;
}
}
};