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

• ``````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;
}
};
``````

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