题解 | #最小覆盖子串#
最小覆盖子串
http://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac
class Solution {
public:
/**
*
* @param S string字符串
* @param T string字符串
* @return string字符串
*/
string minWindow(string S, string T) {
int left = 0, right = 0;
//表示窗口左右位置的指针
int start = 0, minLen = INT_MAX;
//start 表示最后结果字符串开始位置，minlen表示最后字符串长度，二者可以表示一个字符串
unordered_map<char, int> need;
//need的存放字符串T的所有字符统计
unordered_map<char, int> window;
//window 存放现有的窗口中出现在need中的字符统计
for (auto i:T)
need[i]++;
int match = 0;
//window与need的匹配度
while (right < S.length()) {
char c1 = S[right];
if (need.count(c1)) { // 看need字典中是否存在c1
window[c1]++;
if (window[c1] == need[c1]) // 如果窗口中出现的c1次数等于T字符串中的次数
match++;
}
right++;
while (match == need.size()) { // 此处是need.size()不是T.size()，考虑到T中可能存在重复字符的因素
//当匹配度等于need.size(),说明这段区间可以作为候选结果，更新ret
if (right - left < minLen) {
minLen = right - left;
start = left;
}
char c2 = S[left];
if (need.count(c2)) {
window[c2]--;
if (window[c2] < need[c2])
match--;
}
left++;
}
}
return minLen == INT_MAX ? "" : S.substr(start, minLen);
}
};
查看14道真题和解析
阿里云成长空间 781人发布
