C++ code for follow-up question (Touch every character only Once!!!)


  • 0
    W

    The general idea is to group k strings into 26 buckets, each of which includes candidate strings with the same "next" character that needs to be compared with "next" character of t. Here comes code first:

    vector<bool> isSubsequence(vector<string> ss, string t) {
    	vector<string::const_iterator> iters(ss.size());
    	vector<vector<int> > waitingList(26);
    	int unfinished = ss.size();
    	for(int i = 0; i < ss.size(); i++) {
    		iters[i] = ss[i].begin();
    		if(iters[i] != ss[i].end()) waitingList[*iters[i] - 'a'].push_back(i);
    	}
    	for(char c : t) {
    		vector<int> updateList = waitingList[c - 'a'];
    		waitingList[c - 'a'].clear();
    		for(int i : updateList) {
    			iters[i]++;
    			if(iters[i] != ss[i].end()) waitingList[*iters[i] - 'a'].push_back(i);
    			else unfinished--;
    		}
    		if(unfinished == 0) break;
    	}
    	vector<bool> ans(ss.size());
    	for(int i = 0; i < ss.size(); i++) {
    		ans[i] = iters[i] == ss[i].end();
    	}
    	return ans;
    }
    

    The idea is straightforward. The original idea of this solution should attribute to @haiwei624 . I just made several improvement and test a little.

    1. We should check if an iterator has reached the end of s;
    2. We should consider corner case when s is empty;
    3. Also, we can maintain a counter to record the number of s whose comparison is unfinished. If all s have finished their comparison, we can jump out of the loop. This can be helpful when strings in ss are similar, and t is extremely long, however, the worst case time complexity is still O(len(t) + sum(len(s[i]))). BTW, I think I agree with your time complexity, because every character can and can only be touched once, so that's why, right?

Log in to reply
 

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