首页 > 代码库 > LeetCode "Minimum Window Substring" - STAR
LeetCode "Minimum Window Substring" - STAR
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.
class Solution {public: string minWindow(string S, string T) { if (T.length() > S.length()) return ""; // Build Dict: Yes chars in T could be duplicated unordered_map<char, int> dict; for (int i = 0; i < T.length(); 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_limits<int>::max(); unordered_map<char, size_t> rec; for (int i = 0; i < S.length(); 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 < i && rec[S[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_limits<int>::max()) return ""; return S.substr(minL, minLen); }};
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。