Number of Matching Subsequences

문자열 s와 문자열들이 담긴 벡터를 받는데,

벡터 내의 문자열들이 s의 Subsequence로 만들 수 있다면

몇 개의 문자열이 Subsequence를 만족하는지 구하는 문제이다

이진탐색을 하지 않을 시 시간 초과가 떴다.

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        
        unordered_map<char, vector<int>> hashTable{};
        
        int index{0};
        for (char &c : s)
        {
            hashTable[c].push_back(index++);
        }
        
        int result{0};
        for (string &word : words)
        {
            bool success{true};
            index = -1;
            
            for (char &alphabet : word)
            {
                if (hashTable.count(alphabet) == 0)
                {
                    success = false;
                    break;
                }
                
                auto it = upper_bound(hashTable[alphabet].begin(), hashTable[alphabet].end(), index);
                if (it != hashTable[alphabet].end())
                {
                    index = *it;
                }
                else
                {
                    success = false;
                    break;
                }
            }
            
            if (success)
            {
                result++;
            }
        }
        
        return result;
    }
};