# 792 Number of Matching Subsequences

## 792. [Number of Matching Subsequence](https://leetcode.com/problems/number-of-matching-subsequences/description/)

## 1. Question

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]`.

## 2. Implementation

**(1) Brute Force**

```java
class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int res = 0;

        for (String word : words) {
            if (word.length() > S.length()) continue;

            if (isSubsequence(word, S)) {
                ++res;
            }
        }
        return res;
    }

    public boolean isSubsequence(String t, String s) {
        int tIndex = 0;
        for (int i = 0; i < s.length() && tIndex < t.length(); i++) {
            if (s.charAt(i) == t.charAt(tIndex)) {
                ++tIndex;
            }
        }
        return tIndex == t.length();
    }
}
```

**(2) HashMap + Queue**

```java
class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int res = 0;

        Map<Character, Queue<String>> map = new HashMap<>();

        for (char c : S.toCharArray()) {
            if (!map.containsKey(c)) {
                map.put(c, new LinkedList<>());
            }
        }

        for (String word : words) {
            if (word.length() > S.length()) continue;

            if (map.containsKey(word.charAt(0))) {
                map.get(word.charAt(0)).add(word);
            }
        }

        for (char c : S.toCharArray()) {
            Queue<String> queue = map.get(c);

            int size = queue.size();

            for (int i = 0; i < size; i++) {
                String curWord = queue.remove();

                if (curWord.length() == 1) {
                    ++res;
                }
                else if (map.containsKey(curWord.charAt(1))) {
                    map.get(curWord.charAt(1)).add(curWord.substring(1));
                }
            }
        }
        return res;
    }
}
```

**(3) Memoization**

```java
class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int res = 0;

        Map<String, Boolean> cache = new HashMap<>();

        for (String word : words) {
            if (word.length() > S.length()) continue;

            if (isSubsequence(word, S, cache)) {
                ++res;
            }
        }
        return res;
    }

    public boolean isSubsequence(String word, String S, Map<String, Boolean> cache) {
        if (cache.get(word) != null) {
            return cache.get(word);
        }

        int index = -1;
        for (char c : word.toCharArray()) {
            index = S.indexOf(c, index + 1);

            if (index == -1) {
                cache.put(word, false);
                return false;
            }
        }
        cache.put(word, true);
        return true;
    }
}
```

## 3. Time & Space Complexity

**Brute Force:** 时间复杂度O(nL), n为word的个数，L为S的长度， 空间复杂度O(1)

**HashMap + Queue:** 时间复杂度O(nL), 空间复杂度O(n)

**Memoization:** 时间复杂度O(nL), 空间复杂度O(n)