Share my ugly Accepted code -,-


  • 1
    W
    class Solution {
    public:
        string minWindow(string S, string T) {
            const int maxc = 256;
    
            int cntT = T.length();
    
            /// cntT == 0
            if (cntT <= 0) return "";
    
            /// queue
            int *Q = new int[S.length()+5];
            int front = 0, tail = 0;
    
            /// queue count
            int *qc = new int[maxc];
            for (int i = 0; i < maxc; ++i) qc[i] = 0;
    
            /// T table
            int *tb = new int[maxc];
            for (int i = 0; i < maxc; ++i) tb[i] = 0;
            for (int i = 0; i < cntT; ++i) ++tb[ T[i] ];
    
            /// ans infrus
            const int INF = 0x7FFFFFFF;
            int curcnt = 0;
            int minLen = INF, sPos;
    
            /// solve
            for (int i = 0; i < S.length(); ++i) {
                char ch = S[i];
                /// ch in T table
                if (tb[ch] > 0) {
                    /// push ch
                    Q[tail++] = i;
                    ++qc[ch];
    
                    /// valid
                    if (qc[ch] <= tb[ch]) ++curcnt;
    
                    /// update ans
                    if (curcnt == cntT) {
                        /// pop
                        ch = S[Q[front]];
                        while (front < tail && qc[ch] > tb[ch]) {
                            --qc[ch];
                            ++front;
                            ch = S[Q[front]];
                        }
                        if (minLen > Q[tail-1] - Q[front]+1) {
                            minLen = Q[tail-1] - Q[front]+1;
                            sPos = Q[front];
                        }
                        /// pop front
                        ch = S[Q[front]];
                        --qc[ch];
                        ++front;
                        --curcnt;
                    }
                }
            }
    
            if (minLen >= INF) return "";
    
            return S.substr(sPos, minLen);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.