0792. Number of Matching Subsequences

题目信息

题号:

0792

难度:

Medium

主题:

字符串、子序列、批量计数

原题:

LeetCode 0792

重点:

子序列允许删除任意字符但必须保持剩余字符相对顺序;按 words 中的元素实例计数,重复单词若匹配需要分别计入

题目重述

给定一个只含小写英文字母的字符串 s 和字符串数组 words。若能从 s 中删除零个或多个字符,并在不改变剩余字符相对顺序的情况下得到某个字符串,则该字符串是 s 的子序列。

请返回 words 中有多少个元素是 s 的子序列。数组中可以出现相同单词,每个位置都独立计数;若一个重复单词匹配,则它的每次出现都应计入答案。

1 <= s.length <= 5 * 10^4,1 <= words.length <= 5000,1 <= words[i].length <= 50。

自建示例

重复单词按出现次数分别统计:

输入:s = "abracadabra", words = ["ada","aaa","baa","drr","ada"]
输出:4
解释:"ada" 的两次出现都能按顺序从 s 中选出;"aaa" 和 "baa" 也都是子序列。"drr" 在 d 之后找不到两个 r,因此不匹配。

所有候选都不匹配:

输入:s = "a", words = ["b","aa"]
输出:0
解释:单字符 b 与 s 的字符不同;"aa" 需要两个按顺序出现的 a,而 s 只有一个字符。因此两个候选都不是子序列。