C++ preprocess O(n) and processing O(n*log(m)) follow up question


  • 0
    class Solution {
    public:
        //binary search next great index
        int findNextGreaterThan(const vector<int> & dp, const int & index){
            if(index >= dp.back()){
                return -1;
            }else if(index < dp[0]){
                return dp[0];
            }else{
                int left = 0, right = dp.size()-1, pivot = left + (right-left)/2;
                while(left!=right){
                    if(dp[pivot] == index){
                        return dp[pivot+1];
                    }else if(dp[pivot] < index){
                        left = pivot+1;
                    }else{
                        right = pivot;
                    }
                    pivot = left + (right-left)/2;
                }
                return dp[left];
            }
        }
        map<char, vector<int>> dp;
        bool isSubsequence(string s, string t) {
            //preprocessing
            for(int i = 0;i<t.size();++i){
                char c = t.at(i);
                if(dp.find(c)==dp.end())
                    dp[c] = vector<int>();
                dp[c].push_back(i);
            }
            //main process
            int i = -1;
            for(char c:s){
                if(dp.find(c) == dp.end())
                    return false;
                int next = findNextGreaterThan(dp[c],  i);
                if(next == -1)
                    return false;
                else
                    i = next;
            }
            return true;
        }
    };
    

Log in to reply
 

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