【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×len(s))O(len(s) + N\times len(s))O(len(s)+N×len(s))，其中NNN是wordswordswords中所有单词的个数
• 空间复杂度O(len(s))O(len(s))O(len(s))

AC代码

C++

class Solution {
public:int numMatchingSubseq(string& s, vector& words) {vector 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::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"]

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

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

将它们分别后移一位：

• 0号指针对应字符串为a，指针后移一位达到了字符串的末尾，也就是说0号指针把字符串a“指完了”，因此a是s的子序列
• 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)O(len(s) + N)O(len(s)+N)，其中NNN是wordswordswords中所有单词的个数
• 空间复杂度O(N+C)O(N + C)O(N+C)，其中CCC是字符种类数小写字母个数262626

AC代码

C++

class Solution {
public:int numMatchingSubseq(string& s, vector& words) {queue q[26];  // q[0]: 下一个是'a'的word在words中的indexfor (int index = 0; index < words.size(); index++)q[words[index][0] - 'a'].push(index);vector 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