[C++] Build the sorted table and do binary search 68ms


  • 0
    C
    class Solution {
    public:
        void go(int s, int val, vector<vector<int>> &L, int tt, int &st, int &len, int &ed, bool &find){
            if(s < 0){ // walk to the beginning of string T
                find = true;
                if(tt-val < len){ // record the length and update the starting and ending position
                    len = tt-val;
                    st = val;
                    ed = tt;
                }
                else if(tt-val == len && val < st){
                    st = val;
                    ed = tt;
                }
                return ;
            }
            int l(L[s].size());
            if(l == 0) return ;
            // Do binary search to find the index which is smaller. If it is equal, decrease one.
            int left = 0, right = l-1;
            while(left <= right){
                int mid = left+(right-left)/2;
                if(L[s][mid] > val){
                    right = mid-1;
                }
                else{
                    left = mid+1;
                }
            }
            if(L[s][right] == val) --right;
            if(right < 0) return ;
            go(s-1, L[s][right], L, tt, st, len, ed, find);
        }
        string minWindow(string S, string T) {
            vector<vector<int>> L;
            int n(S.size()), m(T.size());
            L.resize(m);
            // build the sorted list O(ST)
            for(int i=0;i<n;++i)
                for(int j=0;j<m;++j)
                    if(S[i] == T[j])
                        L[j].push_back(i);
            
            int st(n), len(n), ed;
            string ans("");
            bool find(false);
            // do binary search O(T logS)
            for(int i=0;i<L[m-1].size();++i)
                go(m-2, L[m-1][i], L, L[m-1][i], st, len, ed, find);
            
            if(find)
                for(int i=st;i<=st+len;++i)
                    ans.append(1, S[i]);
            return ans;
        }
    };
    

Log in to reply
 

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