792. Number of Matching Subsequences

问题：

给定一个字符串S，和一个词组集合words，返回words里的字符串为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].

解法：

创建一个待判断字符map，对于S的每一个字符，

在待判断字符map中寻找，是否有这样的字符待判断，

若有，则该字符下所有的words字串向后偏移一位，更新下一位待判断字符。

说明：

1.待判断字符map

初始化：

{
{a : ["a", "acd", "ace"]},
{b: ["bb"]}
}
res=0

逐次判断S="abcde"的各位字符

首先第一个字符'a'

则在map中找到有三个字串都待判断首字母为'a'

那么更新map：将这三个字符串向后偏移一位，同时重新插入map中。

⚠️注意：这里如果字串的长度==1，那么找到我们的目标字串，res++（这里举例为“a”）

{
{c: ["cd", "ce"]},
{b: ["bb"]}
}
res++（0->1  “a”）

S的下一个字符'b'

{
{c: ["cd", "ce"]},
{b: ["b"]}
}
res=1

S的下一个字符'c'

{
{d: ["d"]},
{e: ["e"]},
{b: ["b"]}
}
res=1

S的下一个字符'd'

{
{e: ["e"]},
{b: ["b"]}
}
res++ (1->2 "acd")

S的下一个字符'e'

{
{b: ["b"]}
}
res++ (2->3 "ace")

随着S遍历完毕，可返回res=3

参考代码：

class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
        int res=0;
        int i=0, j=0, k=0;
        map<char,vector<string>> wait;
        for(i=0; i<words.size(); i++){
            wait[words[i][0]].push_back(words[i]);
        }
        for(k=0; k<S.length(); k++){
            char checkv=S[k];
            vector<string> tmp=wait[checkv];
            wait[checkv].clear();
            for(i=0; i<tmp.size(); i++){
                if(tmp[i].length()==1) {
                    res++;
                }
                else wait[tmp[i][1]].push_back(tmp[i].substr(1));
            }
        }
        return res;
    }
};