线上推广图片_软件工程可以做什么工作_新媒体运营师证书_全球中文网站排名

题目描述：

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

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

代码思路：

1. 初始化变量：
   • ret：用于存储结果，即满足条件的子串数量。
   • std_count：一个字典，用于存储 word2 中每个字符的出现次数，作为我们的“标准”或“参照”。
   • 检查 word2 的长度是否大于 word1 的长度，如果是，则直接返回 0，因为较短的字符串不可能包含较长的字符串作为其子序列。
2. 构建标准字典：
   • 遍历 word2，构建一个字典 std_count，其中键是 word2 中的字符，值是该字符在 word2 中出现的次数。
3. 滑动窗口的设置：
   • st 和 ed：分别表示滑动窗口的起始和结束位置。
   • window：一个字典，用于跟踪当前窗口（即当前考虑的子串）中每个字符的出现次数。
   • valid：一个计数器，表示当前窗口中已经满足 std_count 中要求的字符个数（即字符出现次数与 std_count 中一致）。
4. 滑动窗口过程：
   • 使用 while 循环遍历 word1，通过移动 ed 来扩展窗口。
   • 对于每个新加入的字符（word1[ed]），检查它是否在 std_count 中。如果是，则更新 window 字典中该字符的计数。
   • 如果某个字符在 window 中的计数与 std_count 中的计数相匹配，则增加 valid 计数器。
   • 当 valid 计数器的值等于 std_count 字典的长度时，表示当前窗口已经包含了 word2 中的所有字符，且每种字符的出现次数都符合要求。
   • 在这种情况下，可以开始收缩窗口（通过移动 st），同时更新 window 和 valid。对于每个收缩步骤，都可以将当前窗口及其右侧的所有子串视为满足条件的子串，因此将 (len(word1) - ed) 加到 ret 上。
   • 继续扩展窗口，直到 ed 遍历完整个 word1。
5. 返回结果：
   • 返回 ret，即满足条件的子串总数。

代码实现：

class Solution:def validSubstringCount(self, word1: str, word2: str) -> int:ret = 0std_count = dict() #参照if len(word2)>len(word1):return retfor i in word2:std_count[i] = std_count.get(i,0) + 1st = 0ed = 0window = dict()valid = 0while ed<len(word1):tmp = word1[ed]if tmp in std_count:window[tmp] = window.get(tmp,0) + 1if window[tmp] == std_count[tmp]: #窗口内满足某一元素个数要求valid += 1while valid==len(std_count): #满足前缀和要求，开始收缩tmp = word1[st]if tmp in window:window[tmp] -= 1if window[tmp] < std_count[tmp]:valid -= 1ret += (len(word1)-ed)st += 1ed += 1return ret