匹配子序列的单词数
难度:
标签:
题目描述
代码结果
运行时间: 122 ms, 内存: 17.6 MB
/*
* Problem: Given a string `s` and an array of strings `words`, return the number of words[i] that are subsequences of `s`.
*
* Approach: Using Java Streams to filter and count words that are subsequences of `s`.
* We use a helper method to check if a word is a subsequence of `s`.
*/
import java.util.Arrays;
public class Solution {
public long numMatchingSubseq(String s, String[] words) {
return Arrays.stream(words)
.filter(word -> isSubsequence(word, s))
.count();
}
private boolean isSubsequence(String word, String s) {
int i = 0, j = 0;
while (i < word.length() && j < s.length()) {
if (word.charAt(i) == s.charAt(j)) {
i++;
}
j++;
}
return i == word.length();
}
}
解释
方法:
这个题解的思路是先用Counter统计words中每个单词出现的次数,然后对于每个单词,在s中查找其字符是否能按顺序出现。如果某个字符找不到,就将该单词的计数从总数n中减去。最后返回n作为最终结果,即s的子序列的单词个数。
时间复杂度:
O(m + len(s) * unique(words))
空间复杂度:
O(m + unique(words))
代码细节讲解
🦆
为什么题解选择在找不到字符时直接减去该单词的计数,这种处理方式是否可能导致对最终计数的误差?
▷🦆
在使用`s.find()`进行字符查找时,如果`s`非常长而单词比较短,这种方法的效率如何?是否存在性能瓶颈?
▷🦆
考虑到查找单词中每个字符的顺序出现,是否有更高效的数据结构或算法来替代直接使用`s.find()`方法?
▷相关问题
判断子序列
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"
是"abcde"
的一个子序列,而"aec"
不是)。
进阶:
如果有大量输入的 S,称作 S1, S2, ... , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?
致谢:
特别感谢 @pbrother 添加此问题并且创建所有测试用例。
示例 1:
输入:s = "abc", t = "ahbgdc" 输出:true
示例 2:
输入:s = "axc", t = "ahbgdc" 输出:false
提示:
0 <= s.length <= 100
0 <= t.length <= 10^4
- 两个字符串都只由小写字符组成。