标签: 字典树 数组 哈希表 字符串 二分查找 动态规划 排序
难度: Medium
给定字符串 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 * 1041 <= words.length <= 50001 <= words[i].length <= 50words[i]和 s 都只由小写字母组成。运行时间: 122 ms
内存: 17.6 MB
class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
n = len(words)
counter = Counter(words)
for k,v in counter.items():
i = 0
for c in k:
i = s.find(c,i) + 1
if not i:
n -= counter[k]
break
return n
这个题解的思路是先用Counter统计words中每个单词出现的次数，然后对于每个单词，在s中查找其字符是否能按顺序出现。如果某个字符找不到，就将该单词的计数从总数n中减去。最后返回n作为最终结果，即s的子序列的单词个数。
时间复杂度: O(m + len(s) * unique(words))
空间复杂度: O(m + unique(words))
class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
n = len(words)
counter = Counter(words) # 统计每个单词出现的次数
for k,v in counter.items(): # 遍历每个不同的单词
i = 0
for c in k: # 查找单词的每个字符是否能在s中按顺序出现
i = s.find(c,i) + 1
if not i: # 如果某个字符找不到
n -= counter[k] # 将该单词的计数从总数中减去
break
return n # 返回最终的子序列单词个数
题解中这种处理方式是基于这样的逻辑：如果在字符串s中找不到单词k的某个字符，那么单词k不可能作为s的子序列。因此，每当发现单词k中的某个字符在s中找不到时，可以确定这个单词不是s的有效子序列，从而将其计数直接从总数n中减去。这种处理方式不会导致误差，因为每个单词都是独立被检查的，且一旦确定某个单词不是子序列，其对总计数的贡献就应该被移除。这是一种准确且高效的处理策略，避免了对不可能的子序列进行不必要的计算。
使用`s.find()`方法进行字符查找可以在字符串s中有效查找指定字符的位置。然而，如果字符串s非常长，这种方法可能会成为性能瓶颈。每次调用`s.find()`都可能需要遍历字符串s的大部分或全部以找到字符，这在最坏情况下是线性时间复杂度。如果words中含有许多单词，那么每个单词都可能需要执行多次`s.find()`操作，导致整体算法的时间复杂度较高。特别是在s的长度远大于单词长度时，这种效率问题尤为明显，因为每次查找操作都可能涉及大量的字符遍历。
有几种更高效的数据结构和算法可以用来优化查找单词中每个字符的顺序出现的问题。一种方式是使用哈希表预先存储字符串s中每个字符出现的所有索引，然后对于每个单词，利用这些索引来快速确定字符是否按顺序存在。另一种方法是构建一个基于字符的邻接表，称为'前向索引'，它允许您快速跳转到下一个字符的位置而不是线性搜索。此外，可以使用二分搜索在预存的索引列表中查找下一个字符的位置，从而减少查找时间。这些方法可以显著提高算法处理大规模数据的能力，尤其是在s很长的情况下。