792. 匹配子序列的单词数
题目描述
输入字符串 s 和字符串数组 words。
若从 s 中删去零个或多个字符、其余字符保持原有顺序后能得到某个字符串，就称它是 s 的子序列。比如 "ace" 是 "abcde" 的子序列。
返回 words 中是 s 的子序列的元素个数。words 中相同的单词各自计数。
示例 1
输入：s = "abcde", words = ["a","bb","acd","ace"] 输出：3
解释："a"、"acd"、"ace" 是子序列，"bb" 不是。
示例 2
输入：s = "dsahjpjauf" words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"] 输出：2
解释：只有 "ahjpjau" 和 "ja" 能在 s 中按顺序找到。
数据范围
1 <= s.length <= 5 * 10^41 <= words.length <= 50001 <= words[i].length <= 50words[i]和s只含小写字母。
解题思路：多指针分桶
对每个单词单独双指针匹配要扫 s 很多遍。换个角度：只扫一遍 s，让所有单词同时匹配。每个单词都在“等”自己的下一个字符，把它挂到这个字符的桶里。读到 s 的字符 c 时，取出 c 桶里的全部单词，各自前进一位：走到末尾就计数，否则挂到新的“下一个字符”桶里。
为什么正确
读完 s 的前缀后，每个未完成的单词恰好在一个桶里，桶名是它下一个需要匹配的字符，且已匹配部分是贪心能匹配的最长前缀。
复杂度分析
时间 O(|s| + 所有单词总长)，空间 O(单词数)。
易错点
处理 c 桶时必须先把桶“摘下来”换成空桶，再遍历旧桶。否则如果单词下一个字符还是 c（比如 "bb"），它会被放回正在遍历的桶里，在同一个 s 字符上被重复匹配。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
waiting = defaultdict(list)
for w in words:
waiting[w[0]].append((w, 0))
ans = 0
for c in s:
bucket = waiting[c]
waiting[c] = []
for w, i in bucket:
i += 1
if i == len(w):
ans += 1
else:
waiting[w[i]].append((w, i))
return ansclass Solution {
public int numMatchingSubseq(String s, String[] words) {
List<List<int[]>> waiting = new ArrayList<>();
for (int c = 0; c < 26; c++) waiting.add(new ArrayList<>());
for (int j = 0; j < words.length; j++) {
waiting.get(words[j].charAt(0) - 'a').add(new int[]{j, 0});
}
int ans = 0;
for (char c : s.toCharArray()) {
List<int[]> bucket = waiting.get(c - 'a');
waiting.set(c - 'a', new ArrayList<>());
for (int[] p : bucket) {
int j = p[0], i = p[1] + 1;
if (i == words[j].length()) {
ans++;
} else {
waiting.get(words[j].charAt(i) - 'a').add(new int[]{j, i});
}
}
}
return ans;
}
}class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
vector<vector<pair<int, int>>> waiting(26);
for (int j = 0; j < (int)words.size(); j++) {
waiting[words[j][0] - 'a'].push_back({j, 0});
}
int ans = 0;
for (char c : s) {
vector<pair<int, int>> bucket;
swap(bucket, waiting[c - 'a']);
for (auto [j, i] : bucket) {
i++;
const string& w = words[j];
if (i == (int)w.size()) {
ans++;
} else {
waiting[w[i] - 'a'].push_back({j, i});
}
}
}
return ans;
}
};func numMatchingSubseq(s string, words []string) int {
waiting := make([][][2]int, 26)
for j, w := range words {
waiting[w[0]-'a'] = append(waiting[w[0]-'a'], [2]int{j, 0})
}
ans := 0
for _, c := range s {
bucket := waiting[c-'a']
waiting[c-'a'] = nil
for _, p := range bucket {
j, i := p[0], p[1]+1
if i == len(words[j]) {
ans++
} else {
idx := words[j][i] - 'a'
waiting[idx] = append(waiting[idx], [2]int{j, i})
}
}
}
return ans
}var numMatchingSubseq = function(s, words) {
const waiting = new Map();
const push = (c, item) => { if (!waiting.has(c)) waiting.set(c, []); waiting.get(c).push(item); };
for (const w of words) {
push(w[0], [w, 0]);
}
let ans = 0;
for (const c of s) {
const bucket = waiting.get(c) || [];
waiting.set(c, []);
for (let [w, i] of bucket) {
i++;
if (i === w.length) {
ans++;
} else {
push(w[i], [w, i]);
}
}
}
return ans;
};function numMatchingSubseq(s: string, words: string[]): number {
const waiting = new Map<string, [string, number][]>();
const push = (c: string, item: [string, number]) => { if (!waiting.has(c)) waiting.set(c, []); waiting.get(c).push(item); };
for (const w of words) {
push(w[0], [w, 0]);
}
let ans = 0;
for (const c of s) {
const bucket = waiting.get(c) || [];
waiting.set(c, []);
for (let [w, i] of bucket) {
i++;
if (i === w.length) {
ans++;
} else {
push(w[i], [w, i]);
}
}
}
return ans;
}其他解法
分桶法只扫一遍 s，所有单词一起推进，需要提前拿到全部单词；二分法预处理 s 后逐个单词查询，适合单词在线到来的情形。
解法 2：位置表 + 二分查找 时间 O(|s| + Σ|w|·log|s|)，空间 O(|s|)
预处理 s，把每个字母出现的下标按升序存成列表。判断一个单词时，维护上一个匹配位置 p（初始为 -1），对每个字母在它的下标列表中二分查找第一个大于 p 的下标，找不到就不是子序列，找到就更新 p。
每个单词独立判断，可以在线处理不断到来的查询，是“判断子序列”进阶问题的标准解法。比分桶法多一个 log|s| 因子。
from bisect import bisect_right
class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
pos = [[] for _ in range(26)]
for i, c in enumerate(s):
pos[ord(c) - 97].append(i)
ans = 0
for w in words:
p = -1
ok = True
for c in w:
lst = pos[ord(c) - 97]
j = bisect_right(lst, p)
if j == len(lst):
ok = False
break
p = lst[j]
if ok:
ans += 1
return ansclass Solution {
public int numMatchingSubseq(String s, String[] words) {
List<List<Integer>> pos = new ArrayList<>();
for (int c = 0; c < 26; c++) pos.add(new ArrayList<>());
for (int i = 0; i < s.length(); i++) pos.get(s.charAt(i) - 'a').add(i);
int ans = 0;
for (String w : words) {
int p = -1;
boolean ok = true;
for (int k = 0; k < w.length() && ok; k++) {
List<Integer> lst = pos.get(w.charAt(k) - 'a');
int lo = 0, hi = lst.size();
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (lst.get(mid) <= p) lo = mid + 1;
else hi = mid;
}
if (lo == lst.size()) ok = false;
else p = lst.get(lo);
}
if (ok) ans++;
}
return ans;
}
}class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
vector<vector<int>> pos(26);
for (int i = 0; i < (int)s.size(); i++) pos[s[i] - 'a'].push_back(i);
int ans = 0;
for (const string& w : words) {
int p = -1;
bool ok = true;
for (char c : w) {
auto& lst = pos[c - 'a'];
auto it = upper_bound(lst.begin(), lst.end(), p);
if (it == lst.end()) {
ok = false;
break;
}
p = *it;
}
if (ok) ans++;
}
return ans;
}
};func numMatchingSubseq(s string, words []string) int {
pos := make([][]int, 26)
for i := 0; i < len(s); i++ {
pos[s[i]-'a'] = append(pos[s[i]-'a'], i)
}
ans := 0
for _, w := range words {
p := -1
ok := true
for k := 0; k < len(w); k++ {
lst := pos[w[k]-'a']
j := sort.SearchInts(lst, p+1)
if j == len(lst) {
ok = false
break
}
p = lst[j]
}
if ok {
ans++
}
}
return ans
}var numMatchingSubseq = function(s, words) {
const pos = Array.from({ length: 26 }, () => []);
for (let i = 0; i < s.length; i++) pos[s.charCodeAt(i) - 97].push(i);
let ans = 0;
for (const w of words) {
let p = -1, ok = true;
for (let k = 0; k < w.length && ok; k++) {
const lst = pos[w.charCodeAt(k) - 97];
let lo = 0, hi = lst.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (lst[mid] <= p) lo = mid + 1;
else hi = mid;
}
if (lo === lst.length) ok = false;
else p = lst[lo];
}
if (ok) ans++;
}
return ans;
};function numMatchingSubseq(s: string, words: string[]): number {
const pos: number[][] = Array.from({ length: 26 }, () => []);
for (let i = 0; i < s.length; i++) pos[s.charCodeAt(i) - 97].push(i);
let ans = 0;
for (const w of words) {
let p = -1, ok = true;
for (let k = 0; k < w.length && ok; k++) {
const lst = pos[w.charCodeAt(k) - 97];
let lo = 0, hi = lst.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (lst[mid] <= p) lo = mid + 1;
else hi = mid;
}
if (lo === lst.length) ok = false;
else p = lst[lo];
}
if (ok) ans++;
}
return ans;
}