> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/string/792.number-of-matching-subsequences.md).

# 792.Number-of-Matching-Subsequences

## 792. Number of Matching Subsequences

## 题目地址

<https://leetcode.com/problems/number-of-matching-subsequences/>

## 题目描述

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

## 代码

### Approach #1 Next Letter Pointers

Time: O(*S*.length+∑words\[i].length) && Space: O(*S*.length)

```java
class Solution {
  public int numMatchingSubseq(String S, String[] words) {
        int ans = 0;
    ArrayList<Node>[] heads = new ArrayList[26];
    for (int i = 0; i < 26; i++) {
      heads[i] = new ArrayList<Node>();
    }

    for (String word: words) {
      heads[word.charAt(0) - 'a'].add(new Node(word, 0));
    }

    for (char c: S.toCharArray()) {
      ArrayList<Node> old_bucket = heads[c - 'a'];
      heads[c - 'a'] = new ArrayList<Node>();

      for (Node node: old_bucket) {
        node.index++;
        if (node.index == node.word.length()) {
          ans++;
        } else {
          heads[node.word.charAt(node.index) - 'a'].add(node); 
        }
      }
      old_bucket.clear();
    }
    return ans;
  }
}

class Node {
  String word;
  int index;
  public Node(String w, int i) {
    word = w;
    index = i;
  }
}
```

### Approach #2 Brute Force \[Time Limit Exceeded]

```java
class Solution {
  char[] ca, cb;
  public int numMathingSubseq(String S, String[] words) {
    int ans = 0;
    ca = S.toCharArray();
    for (String word: words) {
      if (subseq(word))        ans++;
    }
    return ans;
  }

  public boolean subseq(String word) {
    int i = 0;
    cb = word.toCharArray();
    for (char c: ca) {
      if (i < cb.length && c == cb[i])        i++;
    }
    return (i == cb.length);
  }
}
```