3 lines C


  • 53
    bool isSubsequence(char* s, char* t) {
        while (*t)
            s += *s == *t++;
        return !*s;
    }
    

    Just go through t and "cross off" the matching characters in s. Then return whether there's nothing left in s.

    Sometimes, C makes things easier... here it's helpful that C strings are null terminated and that I can easily pop off a string's first character in constant time just by incrementing the pointer.


  • 0

  • 5

    @StefanPochmann
    Thanks for your awesome answer and how about the follow-up?


  • 16

    @Th111 for your question,
    First, here is a C++ version:
    O(len(t))

    class Solution {
    public:
        bool isSubsequence(string s, string t) {
        	auto i = s.begin();
            for(char c : t) i += (*i == c);
            return i == s.end();
        }
    };
    

    For the Follow-up, assume we have S1...Sk, above C++ code can be change to a simple follow-up version:
    Follow-up, O(len(t) * k)

    class Solution {
    public:
        vector<bool> isSubsequence(vector<string> ss, string t) {
        	vector<string::const_iterator> iters(ss.size());
        	for(int i = 0; i < ss.size(); i++) {
        		iters[i] = ss[i].begin();
        	}
            for(char c : t) {
            	for(int i = 0; i < ss.size(); i++) {
            		iters[i] += *iters[i] == c;
            	}
            }
            vector<bool> ans(ss.size());
            for(int i = 0; i < ss.size(); i++) {
            	ans[i] = iters[i] == ss[i].end();
            }
            return ans;
        }
    };
    

    If you want to make it faster, you can improve it by avoid unnecessary compare:
    Follow-up Faster, O(len(t) + sum(len(s[i])))

    class Solution {
    public:
        vector<bool> isSubsequence(vector<string> ss, string t) {
        	vector<string::const_iterator> iters(ss.size());
        	vector<vector<int> > waitingList(26);
        	for(int i = 0; i < ss.size(); i++) {
        		iters[i] = ss[i].begin();
        		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]++;
            		waitingList[*iters[i] - 'a'].push_back(i);
            	}
            }
            vector<bool> ans(ss.size());
            for(int i = 0; i < ss.size(); i++) {
            	ans[i] = iters[i] == ss[i].end();
            }
            return ans;
        }
    };
    

  • 3
    W

    @haiwei624 Hi, I made several improvement on your code. Hope it is useful.

    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?
      Here I provide my code, please correct me if anybody find a bug.
    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;
    }
    

  • 0

    I am wondering what do you think in terms of the follow up?


  • 1

    Congrats on the 10k th reputation! Thanks for sharing those amazing solutions all the time!


  • 1
    K

    @haiwei624
    c++ string is not like c array that dereferencing the end() iterator is undefined behavior. should jump out the loop when i reach s.end()

    class Solution {
    public:
        bool isSubsequence(string s, string t) {
        	auto i = s.begin();
            for(char c : t) i += (*i == c);
            return i == s.end();
        }
    };
    

  • 0

    @StefanPochmann same question, how about the follow-up?


  • 0
    W

    @coca-cola Hi, here is my idea for the follow up

    Binary search:

    • record the indexes for each character in t, if s[i] matches t[j], then s[i+1] should match a character in t with index bigger than j. This can be reduced to find the first element larger than a value in an sorted array (find upper bound), which can be achieved using binary search.

    Trie:

    • For example, if s1 has been matched, s1[last char] matches t[j]. Now, s2 comes, if s1 is a prefix of s2, i.e., s1 == s2.substr[0, i-1], we can start match s2 from s2[i], right?
      So, the idea is to create a Trie for all string that have been matched so far. At a node, we record the position in t which matches this char represented by the node. Now, for an incoming string s, we first search the longest prefix in the Trie, find the matching position of the last prefix-char in t, say j. Then, we can start matching the first non-prefix-char of s from j+1.
      Now, if we have done the preprocessing as stated in the binary search approach, we can be even faster.

  • 0

    @wangxinbo thanks for your detailed explanation


  • 0
    H

    Suggesting an optimization where we terminate if we reach end of s:
    bool isSubsequence(char* s, char* t) {
    while (*t && *s)
    s += *s == *t++;
    return !*s;
    }


  • 0
    K

    JS equivalent

    var isSubsequence = function(s, t) {
        while (t.length) {
            s = s.slice(s[0] === t[0]);
            t = t.slice(1);
        }
        return !s.length;    
    };
    

  • 0

    @kodejuice What's the complexity of .slice(1)? (I don't know where to look this up...)


  • 0
    K

    @StefanPochmann .slice() is O(N) where N is end - start


  • 0

    @kodejuice What are "end" and "start"?


  • 0
    K

    .slice(start[, end=endOfArray])

    Anyway i wrote the solution as a near-direct equivalent of your C code....here is a faster JS version

    var isSubsequence = function (s, t){
        let i = 0;
        for (let c=0; c<t.length; c+=1){
            i += s[i] === t[c];
            if (i === s.length)
                return true;
        }
        return i === s.length;
    }
    

  • 0

    @haiwei624 said in 3 lines C:

    iters[i] += *iters[i] == c;

    Could you kindly elaborate the above statement? *iters[i] == c will return either a true or a false. How (and why) do you add it to iters[i]?


  • 0

    @haiwei624 Your follow-up solutions reminds me of a bingo game;


Log in to reply
 

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