LeetCode "Minimum Window Substring" - STAR
2020-12-13 06:28
标签:style blog http color io for 2014 ar Main reference: http://zhaohongze.com/wordpress/2014/01/04/leetcode-minimum-window-substring/ The ART of counting. So difficult and beautiful problem. It is all about dynamic window maintanence. Essentially, it is still a fancy linear scanning procedure. LeetCode "Minimum Window Substring" - STAR,搜素材,soscw.com LeetCode "Minimum Window Substring" - STAR 标签:style blog http color io for 2014 ar 原文地址:http://www.cnblogs.com/tonix/p/3906850.htmlclass Solution {
public:
string minWindow(string S, string T) {
if (T.length() > S.length()) return "";
// Build Dict: Yes chars in T could be duplicated
unordered_mapchar, int> dict;
for (int i = 0; i )
{
if (dict.find(T[i]) == dict.end()) dict.insert(make_pair(T[i], 1));
else dict[T[i]] ++;
}
// Build Indices - char - cnt
size_t ttlCnt = 0;
int iLeft = 0;
int minL = 0, minLen = std::numeric_limitsint>::max();
unordered_mapchar, size_t> rec;
for (int i = 0; i )
{
char c = S[i];
if (dict.find(c) != dict.end())
{
if (rec.find(c) == rec.end()) rec[c] = 1;
else rec[c] ++;
if (rec[c] == dict[c]) ttlCnt++;
if (ttlCnt == dict.size())
{
// Shrink from Left
while ( dict.find(S[iLeft]) == dict.end() || // irrelavant char?
(iLeft dict[S[iLeft]])) // redundant char?
{
if (dict.find(S[iLeft]) != dict.end())
rec[S[iLeft]] --;
iLeft++;
}
// Update record
if ((i - iLeft + 1) minLen)
{
minL = iLeft;
minLen = (i - iLeft + 1);
}
}
}
}
if (minLen == std::numeric_limitsint>::max()) return "";
return S.substr(minL, minLen);
}
};
文章标题:LeetCode "Minimum Window Substring" - STAR
文章链接:http://soscw.com/essay/33087.html