792.匹配子序列的单词数

【LetMeFly】792.匹配子序列的单词数

力扣题目链接：https://leetcode.cn/problems/number-of-matching-subsequences/

给定字符串 s 和字符串数组 words, 返回  words[i] 中是s的子序列的单词个数 。

字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。

• 例如， “ace” 是 “abcde” 的子序列。

 

示例 1:

输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。

Example 2:

输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2

 

提示:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• words[i]和 s 都只由小写字母组成。

​​​​

方法一：二分查找

方法一的思路是每个字符串单独处理。

首先需要预处理字符串s，记录下来s中每个字母的出现位置。 假如s = "aba"，那么a出现的下标为[0, 2]，b出现的下标为[1]

这样，在处理words中每个字符串的时候，只需要从前到后遍历字符串，在s中二分查找当前遍历到的字母即可。

• 时间复杂度$O(len(s) + N\times len(s))$，其中$N$是$words$中所有单词的个数
• 空间复杂度$O(len(s))$

AC代码

C++

class Solution {
public:
    int numMatchingSubseq(string& s, vector<string>& words) {
        vector<int> a[26];
        for (int i = 0; i < s.size(); i++)
            a[s[i] - 'a'].push_back(i);
        int ans = 0;
        for (string& word : words) {
            bool ok = true;
            int loc = -1;
            for (char c : word) {
                vector<int>::iterator it = lower_bound(a[c - 'a'].begin(), a[c - 'a'].end(), loc + 1);  // 在s中所有出现过字符c的下标中，找到大于loc的第一个下标
                if (it == a[c - 'a'].end()) {
                    ok = false;
                    break;
                }
                loc = *it;
            }
            ans += ok;
        }
        return ans;
    }
};

方法二：多指针

方法二的思路是遍历字符串s，在遍历的过程中，不断将这个字符对应的字符串的指针后移。

例如样例一：s = "abcde", words = ["a","bb","acd","ace"]

首先建立$4$个指针（因为有$4$个字符串）

a
↑

bb
↑

acd
↑

ace
↑

然后建立一个大小为26的队列数组，队列中存放二十六个字母对应的指针

[0]: 0, 2, 3  // 是因为四个指针(0, 1, 2, 3)中，第0、2、3个指针所指的元素为a
[1]: 1  // 是因为四个指针中，第1号指针所指元素为b
[2]:
[3]:
[4]:
...
[25]:

接下来遍历字符串s

s的第一个字母为a，看a的队列，有三个指针0, 2, 3

将它们分别后移一位：

• + ```2```号指针对应字符串为```acd```，指针后移一位，移动到```c```。因此队列```[2]: 2```
  + ```3```号指针对应字符串为```ace```，指针后移一位，移动到```c```。因此队列```[2]: 3```

  [0]:
  [1]: 1 // 是因为四个指针中，第1号指针所指元素为b
  [2]: 2, 3
  [3]:
  [4]:
  
  …
  [25]:

```s```的第二个字母为```b```，看```b```的队列，有一个指针```1```

将它后移一位：

+ ```1```号指针对应字符串为```bb```，指针后移一位，移动到第二个```b```。因此队列```[1]: 1```

[0]:
[1]: 1
[2]: 2, 3
[3]:
[4]:
…
[25]:

```s```的第三个字母为```c```，看```c```的队列，有两个指针```2, 3```

将它们分别后移一位：

+ ```2```号指针对应字符串为```acd```，指针后移一位，移动到```d```。因此队列```[3]: 2```
+ ```3```号指针对应字符串为```ace```，指针后移一位，移动到```e```。因此队列```[4]: 3```

[0]:
[1]: 1
[2]:
[3]: 2
[4]: 3
…
[25]:

```s```的第四个字母为```d```，看```d```的队列，有一个指针```2```

将它后移一位：

+ ```2```号指针对应字符串为```acd```，指针后移一位达到了字符串的末尾，也就是说```2```号指针把字符串```acd```“指完了”，因此```acd```是```s```的子序列

[0]:
[1]: 1
[2]:
[3]:
[4]: 3
…
[25]:

```s```的第五个字母为```e```，看```e```的队列，有一个指针```3```

将它后移一位：

+ ```3```号指针对应字符串为```ace```，指针后移一位达到了字符串的末尾，也就是说```3```号指针把字符串```ace```“指完了”，因此```ace```是```s```的子序列

[0]:
[1]: 1
[2]:
[3]:
[4]:
…
[25]:

字符串```s```遍历结束，```words```中三个字符串是```s```的子序列

+ 时间复杂度$O(len(s) + N)$，其中$N$是$words$中所有单词的个数
+ 空间复杂度$O(N + C)$，其中$C$是字符种类数小写字母个数$26$

### AC代码

#### C++

```cpp
class Solution {
public:
    int numMatchingSubseq(string& s, vector<string>& words) {
        queue<int> q[26];  // q[0]: 下一个是'a'的word在words中的index
        for (int index = 0; index < words.size(); index++)
            q[words[index][0] - 'a'].push(index);
        vector<int> loc(words.size(), 0);  // loc[0]: words[0]该匹配哪个单词了
        int ans = 0;
        for (char c : s) {
            for (int i = q[c - 'a'].size(); i > 0; i--) {
                int index = q[c - 'a'].front();
                q[c - 'a'].pop();
                loc[index]++;
                if (loc[index] == words[index].size()) {
                    ans++;
                    continue;
                }
                q[words[index][loc[index]] - 'a'].push(index);
            }
        }
        return ans;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127908867