## 题目描述：

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

## 解题思路：

dp[x][c]表示S[x]之后字符c第一次出现的位置

## Java代码：

``````class Solution {
public int numMatchingSubseq(String S, String[] words) {
int slen = S.length();
int[] last = new int[26];
int[][] dp = new int[slen + 1][26];
for (int i = 0; i < slen; i++) {
int idx = S.charAt(i) - 'a';
for (int x = last[idx]; x <= i; x++) {
dp[x][idx] = i + 1;
}
last[idx] = i + 1;
}
int cnt = 0;
for (String word: words) {
cnt += check(dp, word);
}
return cnt;
}

public int check(int[][] dp, String word) {
int idx = 0;
int wlen = word.length();
for (int i = 0; i < wlen; i++) {
idx = dp[idx][word.charAt(i) - 'a'];
if (idx == 0) return 0;
}
return 1;
}
}
``````

Pingbacks已关闭。