# 0792. Number of Matching Subsequences
###### tags: `Leetcode` `Medium` `Greedy`
Link: https://leetcode.com/problems/number-of-matching-subsequences/
## 思路
### 原始思路(TLE) $O(N+MKN)$ $O(N)$
N = s.length()
M = words.length()
K = words里面word的平均长度
之所以是MKN不是MK，是因为对于一个字母，要遍历它所有出现的位置
用HashMap存下每个字母以及它对应出现的所有位置
然后对于每个word遍历一遍，用prevPos记录上一个字母出现的位置，对于每一个字母找到最小的但大于prevPos的index，然后更新prevPos，继续向下遍历
### 正确思路 $O(S.length+words.length)$ $O(words.length)$
和[0524. Longest Word in Dictionary through Deleting](https://hackmd.io/hZKZPqUxRyaISwaadQKxeg)一样
先得到next[i][ch]表示s中位置i右边第一个出现ch的位置 这里的时间复杂度是O(26N)
对于word中的每个单词 我们先初始令idx=0 然后一直idx=next[idx][ch] 直到idx=-1为止 如果某个idx=-1 并且还没有到达word的末尾 就说明word不是s的subquence
## Code
正确思路

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int n = s.length();
        int[][] next = new int[n+1][26];
        Arrays.fill(next[n], -1);
        for(int i=n-1; i>=0; i--){
            for(int j=0; j<26; j++){
                next[i][j] = next[i+1][j];
            }
            next[i][s.charAt(i)-'a'] = i+1;
        }
        int ans = 0;
        for(String word:words){
            int idx = 0;
            for(int i=0; i<word.length(); i++){
                idx = next[idx][word.charAt(i)-'a'];
                if(idx==-1) break;
            }
            if(idx!=-1) ans++;
        }
        return ans;
    }
}

HashMap(TLE)

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        Map<Character, List<Integer>> map = new HashMap<>();
        int ans = 0;
        for(int i = 0;i < s.length();i++){
            if(!map.containsKey(s.charAt(i))){
                map.put(s.charAt(i), new ArrayList<>());
            }
            map.get(s.charAt(i)).add(i);
        }
        for(String word:words){
            int prevPos = -1;
            boolean check = true;
            for(int i = 0;i < word.length();i++){
                char c = word.charAt(i);
                int currPos = s.length();
                for(int next:map.getOrDefault(c, new ArrayList<>())){
                    if(next>prevPos && next<currPos){
                        currPos = next;
                    }
                }
                if(currPos==s.length()){
                    check = false;
                    break;
                }
                prevPos = currPos;
            }
            if(check) ans++;
        }
        return ans;
    }
}