CODEWITHSUNDEEP
c++algorithm
kai huang
kai huang

Reputation: 105

lower_bound() return the last element

When I solve the problem of 392.Is Subsequence. on Leetcode.

When I using the function of lower_bound(), I can't understand the difference between I want to find the last element and it doesn't found then return the last element.

This is my code:

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> temp(26);
        for (int i = 0; i < t.length(); ++i)
            temp[t[i]-'a'].push_back(i);
        int index = -1;
        for (int i = 0; i < s.length(); ++i) {
            auto it = upper_bound(temp[s[i]-'a'].begin(), temp[s[i]-'a'].end(), index);

            //if the last element is we want to find what will happen?
            if (it == temp[s[i]-'a'].end()) return false;
            index = *it;
        }
        return true;
    }
};

If the last element is we want to find what will happen?

Upvotes: 1

Views: 345

Answers (1)

Eric
Eric

Reputation: 97601

end() does not point to the last element, it points beyond the last element. Emphasis mine:

Returns an iterator to the end (i.e. the element after the last element) of the given container c or array array.

If the last element is what you want to find, lower_bound will return end() - 1

Upvotes: 2

Related Questions