首页 > 代码库 > 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);    }};