C++, binary search solution for the follow up


  • 0
    bool isSubsequence(string s, string t) {
        vector<vector<int>> idx(26,vector<int>());
        for (int i=0;i<t.size();i++){
            idx[t[i]-'a'].push_back(i);
        }
        int curIdx=-1;
        for(auto&x:s){
            if (idx[x-'a'].empty() || idx[x-'a'].back()<=curIdx) return false;
            int l=0,r=idx[x-'a'].size()-1,mid;
            while(l<r){
                mid = l+(r-l)/2;
                if(idx[x-'a'][mid]>curIdx){
                    r=mid;
                }else{
                    l=mid+1;
                }
            }
            curIdx=idx[x-'a'][l];
        }
        return true;
    }

Log in to reply
 

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