LeetCode 792. 匹配子序列的单词数（二分查找）

示例:
输入: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
输出: 3
解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。

注意:
所有在words和 S 里的单词都只由小写字母组成。
S 的长度在 [1, 50000]。
words 的长度在 [1, 5000]。
words[i]的长度在[1, 50]。

class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
        vector<vector<int>> pos(26);
        for(int i = 0; i < S.size(); i++)
        {
            pos[S[i]-'a'].push_back(i);
        }
        int ans = 0;
        for(auto& w : words)
        {
            int maxpos = -1, j = 0;
            for( ; j < w.size(); j++)
            {
                int idx = w[j]-'a';
                auto it = lower_bound(pos[idx].begin(), pos[idx].end(), maxpos+1);
                if(it == pos[idx].end())
                    break;
                maxpos = *it;
            }
            if(j == w.size())
                ans++;
        }
        return ans;
    }
};