友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
792. 匹配子序列的单词数
给定字符串 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都只由小写字母组成。
思路分析
字符串！
这道题有多种解法：字典树，二分查找，还有如下图的解法：
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-07 21:52:04
*/
public int numMatchingSubseq(String s, String[] words) {
int result = 0;
Map<String, Integer> counter = new HashMap<>();
for (String word : words) {
counter.put(word, counter.getOrDefault(word, 0) + 1);
}
for (Map.Entry<String, Integer> entry : counter.entrySet()) {
String word = entry.getKey();
int si = 0, wi = 0;
while (si < s.length() && wi < word.length()) {
if (s.charAt(si) == word.charAt(wi)) {
wi++;
}
si++;
}
if (wi == word.length()) {
result += entry.getValue();
}
}
return result;
}