Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.
Example : Input: S = "abcde" words = ["a", "bb", "acd", "ace"] Output: 3 Explanation: There are three words in words that are a subsequence of S: "a", "acd", "ace".Note:
All words in words and S will only consists of lowercase letters.The length of S will be in the range of [1, 50000].The length of words will be in the range of [1, 5000].The length of words[i] will be in the range of [1, 50].分析
这道题用暴力搜索是会超时的。需要考虑怎么遍历能够比较好的节省搜索时间。暴力搜索的方法是，记录words中每一个word当前的起始位置start, 从头到尾遍历S，遍历到S[i]时，查看所有words[j][start]是否与S[i]相等。如果相等的话，那么words[j]的起始位置加一。这样的话时间复杂度应该是O(sLen * wordsLen)。
那么考虑如果降低时间复杂度？我们在判断words[i]是不是在S中时，起始只需要找到words[i][j]的字符是不是在S中，并且words[i][j]在S中的位置大于words[i][j-1]在S中的位置。这样的话我们可以使用vector<set<int>> index记录26个字符在S中的位置。然后遍历所有的words，记录words[i]当前字符的最小起始位置start，每一个char c = words[i][j]在index[c - 'a']中寻找是否有大于start的值，如果有，则更新start继续寻找。
Code
class Solution { public: int numMatchingSubseq(string S, vector<string>& words) { int sLen = S.size(); int wordLen = words.size(); vector<set<int>> index(26, set<int>()); for (int i = 0; i < sLen; i ++) { index[S[i] - 'a'].insert(i); } int res = 0; vector<int> dict; for (int i = 0; i < wordLen; i ++) { dict.push_back(-1); } for (int i = 0; i < dict.size(); i ++) { int j = 0; for (j = 0; j < words[i].size(); j ++) { char c = words[i][j]; int start = dict[i]; if (index[c-'a'].upper_bound(start) == index[c-'a'].end()) break; dict[i] = *(index[c-'a'].upper_bound(start)); } if (j == words[i].size()) res ++; } return res; } };运行效率
Runtime: 704 ms, faster than 17.42% of C++ online submissions for Number of Matching Subsequences.
Memory Usage: 137.1 MB, less than 19.98% of C++ online submissions forNumber of Matching Subsequences.
