廊坊seo_黄骅港赶海攻略_百度网址大全官网旧版_种子在线资源搜索神器

题目描述：

给你两个字符串 word1 和 word2 。如果一个字符串 x 重新排列后，word2 是重排字符串的前缀，那么我们称字符串 x 是 合法的 。

请你返回 word1 中 合法子字符串的数目。

注意 ，这个问题中的内存限制比其他题目要 小 ，所以你 必须 实现一个线性复杂度的解法

代码思路：

1. 初始化字符计数器：
   • 使用defaultdict(int)来初始化一个计数器cnt，用于存储word2中每个字符的出现次数。这里选择defaultdict是为了在访问不存在的键时自动返回默认值（这里是0），从而避免KeyError。
2. 统计word2中不同字符的数量：
   • 遍历word2，对每个字符在cnt中计数。同时，用变量cword记录word2中不同字符的数量。
3. 初始化滑动窗口的左右指针和结果变量：
   • l（左指针）和r（右指针）分别初始化为0，用于定义当前考虑的子字符串范围。
   • ans用于累加所有符合条件的子字符串的起始索引数量。
4. 遍历word1，使用滑动窗口寻找符合条件的子字符串：
   • 对于word1中的每个字符（通过右指针r遍历），将其在cnt中的计数减1。
   • 如果某个字符的计数变为0，说明这个字符在当前的子字符串中已经匹配了word2中需要的数量，因此将cword（不同字符的数量）减1。
   • 当cword变为0时，意味着当前窗口内的字符可以组成word2（通过删除一些字符），此时尝试扩展窗口的左边界，直到找到一个不满足条件的字符（即某个字符在word2中的需求未被满足），或者窗口为空。
     • 在尝试扩展左边界的过程中，每次将左指针l指向的字符在cnt中的计数加1，如果计数变为正数，说明这个字符在word2中有需求，因此cword加1。
   • 每次当cword为0时（即找到了一个符合条件的子字符串），将左指针l的值累加到ans中。这里累加l的原因是，以l为起点的任何子字符串（包括空字符串）都可以通过删除一些字符变成word2。例如，如果l是3，那么索引3, 4, 5,...到当前右指针r的子字符串都符合条件（因为从l到r已经是一个完全匹配或超出的集合）。
5. 返回结果：
   • 返回累加的结果ans，即word1中所有符合条件的子字符串（包括空字符串）的起始索引数量总和。

 代码实现：

from collections import defaultdict
class Solution:def validSubstringCount(self, word1: str, word2: str) -> int:# cnt = Counter(word2) 用Counter会慢许多，也能过cnt = defaultdict(int)for word in word2:cnt[word] += 1cword = len(cnt)l, ans = 0, 0for r in word1:cnt[r] -= 1if cnt[r] == 0:cword -= 1while cword == 0:cnt[word1[l]] += 1if cnt[word1[l]] > 0:cword += 1l += 1ans += lreturn ans