# 【LeetCode】792. Number of Matching Subsequences

## 前言
在看到這題題目時，其實就知道這題不能用暴力解，所以我花了一些時間在思考演算法，最終還是以失敗收場，只好看網路上他人的方法。
知道方法後，在寫程式碼時，就非常順利，所以只要掌握好方法，這題就不難。
**絕對不能暴力解，會TLE。**

## 方法
建立一個字典table，a-z為key，value就放多個string 字串。
舉側資為例：

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3

一開始先初始化

a = ["a","acd","ace"]
b = ["bb"]

當指針指到s[0]時 => "a"，就會遍歷key為"a"的陣列，**把字串中的頭刪除**[(方法)](https://)，並把新的字串放到對應的key值，**若字串長度剛好剩1就可以確定這個字串是原本的Subsequence** => `count++`。所以新的table表就會變成

a = []  // count++
b = ["bb"]
c = ["cd","ce"]

指針移動到下一個s[1] => "b"

a = []
b = ["b"]
c = ["cd","ce"]

指針移動到下一個s[2] => "c"

a = []
b = ["b"]
c = []
d = ["d"]
e = ["e"]

指針移動到下一個s[3] => "d"

a = []
b = ["b"]
c = []
d = []  // count++
e = ["e"]

指針移動到下一個s[4] => "e"

a = []
b = ["b"]
c = []
d = []
e = [] // count++

程式到這裡就結束了，雖然table裡面還有東西，但就不需理會，因為剩下的東西不是原字串的子字串，最後count = 3。
## 程式碼

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        map<char,queue<string>> table;
        int count = 0;
        // build table
        for (auto val : words){
            table[val[0]].push(val);
        }
        for (int i=0;i<s.size();i++){
            int currSize = table[s[i]].size();
            for (int j=0;j<currSize;j++){
                string st = table[s[i]].front();
                table[s[i]].pop();
                if (st.size() == 1){
                    count++;
                }
                else{
                    st.erase(0,1);
                    table[st[0]].push(st);
                }    
            }
        }
        return count;
    }
};

###### tags: `LeetCode` `程式`