leetcode
leetcode 701 ~ 750
匹配子序列的单词数

匹配子序列的单词数

难度:

标签:

题目描述

代码结果

运行时间: 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中找不到单词k的某个字符,那么单词k不可能作为s的子序列。因此,每当发现单词k中的某个字符在s中找不到时,可以确定这个单词不是s的有效子序列,从而将其计数直接从总数n中减去。这种处理方式不会导致误差,因为每个单词都是独立被检查的,且一旦确定某个单词不是子序列,其对总计数的贡献就应该被移除。这是一种准确且高效的处理策略,避免了对不可能的子序列进行不必要的计算。
🦆
在使用`s.find()`进行字符查找时,如果`s`非常长而单词比较短,这种方法的效率如何?是否存在性能瓶颈?
使用`s.find()`方法进行字符查找可以在字符串s中有效查找指定字符的位置。然而,如果字符串s非常长,这种方法可能会成为性能瓶颈。每次调用`s.find()`都可能需要遍历字符串s的大部分或全部以找到字符,这在最坏情况下是线性时间复杂度。如果words中含有许多单词,那么每个单词都可能需要执行多次`s.find()`操作,导致整体算法的时间复杂度较高。特别是在s的长度远大于单词长度时,这种效率问题尤为明显,因为每次查找操作都可能涉及大量的字符遍历。
🦆
考虑到查找单词中每个字符的顺序出现,是否有更高效的数据结构或算法来替代直接使用`s.find()`方法?
有几种更高效的数据结构和算法可以用来优化查找单词中每个字符的顺序出现的问题。一种方式是使用哈希表预先存储字符串s中每个字符出现的所有索引,然后对于每个单词,利用这些索引来快速确定字符是否按顺序存在。另一种方法是构建一个基于字符的邻接表,称为'前向索引',它允许您快速跳转到下一个字符的位置而不是线性搜索。此外,可以使用二分搜索在预存的索引列表中查找下一个字符的位置,从而减少查找时间。这些方法可以显著提高算法处理大规模数据的能力,尤其是在s很长的情况下。

相关问题

判断子序列

给定字符串 st ,判断 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
  • 两个字符串都只由小写字符组成。