792 比對子序列的單詞數

題目描述：

給定字元串 S 和單詞字典 words, 求 words[i] 中是 S 的子序列的單詞個數。

示例:

輸入:

S = “abcde”

words = [“a”, “bb”, “acd”, “ace”]

輸出: 3

解釋: 有三個是 S 的子序列的單詞: “a”, “acd”, “ace”。

注意:

所有在words和 S 裡的單詞都隻由小寫字母組成。

S 的長度在 [1, 50000]。

words 的長度在 [1, 5000]。

words[i]的長度在[1, 50]。

方法1：

主要思路：解題連結彙總

（1）桶排序思路；

（2）将出現過的字元使用目前沒有判斷過的最前面的字元存儲到對應buckets中；

（3）周遊S時，每次使用目前字元從buckets中取出一組索引；

（4）若目前的索引指向的單詞已經判斷完了全部的字元，則統計結果加1，否則，使用下一個沒有判斷的字元重新存儲到對應的buckets中；

class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
        vector<vector<pair<int,int>>> buckets(26);
        for(int i=0;i<words.size();++i){//first存儲的是單詞對應的索引，second是目前沒有判斷的最前面的字元的索引
            buckets[words[i][0]-'a'].push_back({i,0});
        }
        int res=0;
        for(char&ch:S){
            vector<pair<int,int>> cur=buckets[ch-'a'];//取出目前字元對應的單詞索引
            buckets[ch-'a'].clear();//情況
            for(pair<int,int>& indexs:cur){//判斷取出的各個單詞
                if(words[indexs.first].size()==indexs.second+1){//說明目前單詞中的字元已經全部判讀完了
                    ++res;
                }
                else{//重新存儲到對應buckets中
                    ++indexs.second;
                    buckets[words[indexs.first][indexs.second]-'a'].push_back({indexs.first,indexs.second});
                }
            }
        }
        return res;
    }
};