Simple C++ code as well as the Followup solution


  • 5
    X
        bool isSubsequence(string s, string t) {
            int si= 0;
            for(int ti = 0; ti < t.size() && si < s.size(); ti++) {
                if(t[ti] == s[si]) si++;
            }
            return si == s.size();
        }
    

    Follow up:
    If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

    My solution is to preprocessing, exactly constructing a hash map to store the positions for every character. Then scan the incoming string one by one, for every character, if there is no such character in the hash map, or the number of such character is greater than the original string, or most critically, the position is not behind the position of its previous character, it will return false. So I need another array to record the index for every character. The time complexity is just the sum of length of incoming strings. If you have better solution, welcome to discuss!

    class Solution {
    public:
        Solution(string t):target(t) {
            for(int i = 0; i < t.length(); ++i) {
                posMap[t[i] - 'a'].push_back(i);
            }
        }
        
        vector<bool> isSubsequence(vector<string> strs) {
            int pre = -1;
            int index[26];
            vector<bool> ans;
            for(string str: strs) {
                memset(index, -1, sizeof(index));
                pre = -1;
                int i = 0;
                for(;i < str.size(); ++i) {
                    int j = str[i] - 'a';
                    if(posMap.find(j) == posMap.end() || posMap[j].size()<= index[j] + 1 || posMap[j][index[j] + 1] <= pre) {
                        ans.push_back(false);
                        break;
                    }
                    pre = posMap[j][index[j] + 1];
                    index[j]++;
                }
                if(i == str.size()) ans.push_back(true);
            }
            return ans;
        }
        
    private:
        string target;
        unordered_map<int, vector<int> > posMap;
    };
    
    
    

  • 0

    I submitted your code, the compiler was complaining, also I don't think " the number of such character is greater than the original string, or most critically, the position is not behind the position of its previous character, it will return false." is right

    • the number (the index or position if I understood correctly) have nothing to do with the original string(index or what?)

    • even if the position(the index of the first time occurrence?) is not behind the position of its previous we can still try to find one afterwords


  • 0
    X

    Thank you for your comment! It can work well on my compiler, what's your compiler say? But I'm sorry that I made a mistake for my explanation, it should be " the number of original character is no less than such string, or most critically, the position is not behind the position of its previous character, it will return false." And I don't think there is something wrong with the last part of the sentence. I held that you misunderstood my idea. I can give you an example.

    s = "a c b d e"
    t = " a b c d"

    1. Initially the previous pos is -1, and for the first character 'a', the pos in original string 0, it's bigger than -1, that's OK and previous pos is set to 0.

    2. For 2nd character 'b', its pos is 2, and also bigger than 0, that's OK and previous pos is set to 2.

    3. For 3rd character 'b', its pos is 1, not bigger than 2, so return false.

    Welcome to correct me. Thanks.


  • 0
    X

    I'm sorry I think I get your meaning this time. And this is the updated code based on your suggestion. It can be accepted. Thanks.

    class Solution {
    public:
    bool isSubsequence(string s, string t) {
        vector<vector<int> > posMap(26);
        // preprocess, store the index for each character
        for(int i = 0; i < t.length(); ++i) {
            posMap[t[i] - 'a'].push_back(i);
        }
        int pre = -1;
        int index[26];
        memset(index, -1, sizeof(index));
        for(int i = 0;i < s.size(); ++i) {
            int j = s[i] - 'a';
            ++index[j];
            // Even if the current index is not appropriate, we can find until the end.
            while(index[j] < posMap[j].size()) {
                if (posMap[j][index[j]] > pre) {
                    break;
                }
                ++index[j];
            }
            
            if(index[j] >= posMap[j].size() ) return false;
        
            pre = posMap[j][index[j]];
        }
        return true;
    };
    
    
    

  • 3

    @xinyao thanks for sharing your code.
    The essential for this problem is that every time we need just find the first available matched character in t.

    bool isSubsequence(string s, string t) {
            vector<vector<int>> char_pos(26);
            for(int i=0; i<t.size(); ++i)
                char_pos[t[i]-'a'].push_back(i);
    
            // remember the previous index of t
            int t_idx = -1;
            for(char c:s){
                int j = c - 'a';
                bool okay = false;
                for(int idx:char_pos[j]){
                    if(idx > t_idx){              
                        // found an available character in t
                        okay = true;
                        t_idx = idx;
                        break;
                    }
                }
                if(okay==false) return false;
            }
            return true;
        }
    

  • 0
    T

    @xinyao said in Simple C++ code as well as the Followup solution:

        // Even if the current index is not appropriate, we can find until the end.
    

    I think you can further improve your code by using binary search when searching the index.


  • 0
    A

    How About this for the follow up; I am storing the index of all the characters in the vector, whenever i am getting a query string i will just compare the characters in query string and find the same in my map, if map doesn't have the entry for the same, then i can straight forward return false, in other case i keep track of monotonically increasing index.

    //Code

     bool isSubsequence(string s, string t) {
            int lenS = s.length();
            int lenT = t.length();
            if(!lenT) return true;
            if(!lenS) return false;
            
            unordered_map<char, vector<int> > mymap;
            
            for(int i =0; i< lenT; i++){
                mymap[t[i]].push_back(i);
            }
            //constructed the map Now check the subsequence
            int prevIndex = -1;
            for(int i =0; i<lenS; i++){
                if(mymap[s[i]].empty()) return false;
                int newIndex=-1;
                int cnt=0;
                while(cnt <mymap[s[i]].size() ){
                    newIndex = mymap[s[i]][cnt++];
                    if(newIndex > prevIndex){
                        prevIndex = newIndex;
                        break;
                    }
                }
                
                if(newIndex == -1 || newIndex < prevIndex)
                    return false;
            }
            
            return true;
            
            
        }
    

Log in to reply
 

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