leetcode分类刷题：滑动窗口（三、两个序列+窗口定长类型）

1、通过对滑动窗口前两个题型的总结，我们几乎已经习惯在给定的一个序列里使用滑动窗口的模板解题了，本次对应的“三、两个序列+窗口定长类型”，也是考察连续子数组、连续子串问题，只不过这次会给定两个序列，判断短序列在长序列中是否存在字母异位词或排列
2、对于这类题目，通常需要先把短子串转为待匹配的哈希表，再定义一个matchKeys标记，计数滑动窗口内的元素与待匹配的哈希表的键的刚好匹配或过匹配的数量（刚好匹配指的是滑窗内该元素在待匹配的哈希表中存在且数量相等，过匹配指的是滑窗内该元素在待匹配的哈希表中存在且数量更多，二者结合就是覆盖的意思）
3、因此，这类题目对应的解法就是：滑动窗口+哈希表+matchKeys标记(刚好匹配或过匹配的键数量)，同时，这类题目直截了当的给出了两个指针如何更新：右指针遍历长序列，左指针在滑窗长度超出短序列

242. 有效的字母异位词

这道题目不是本次的总结题型，放在这里主要是为了给出一下字母异位词的含义：两个序列长度相等，包含的元素种类和数目相同，元素位置不一定相同

'''
242. 有效的字母异位词
题目描述：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若s 和 t中每个字符出现的次数都相同，则称s 和 t互为字母异位词。
示例 1:输入: s = "anagram", t = "nagaram"输出: true
题眼：字母异位词
思路：简单题，直接利用哈希表判断即可
'''class Solution:def isAnagram(self, s: str, t: str) -> bool:# 情况1、两个字符串长度不相等，注意提示字符串长度至少为1if len(s) != len(t):return False# 情况2、两个字符串长度相等hashTable = {}# 将s转换为哈希表for ch in s:if ch in hashTable:hashTable[ch] += 1else:hashTable[ch] = 1# 将t在哈希表中遍历for ch in t:if ch in hashTable:if hashTable[ch] == 0:  # 不删除key的做法，ch字符数量不相等return FalsehashTable[ch] -= 1else:return Falsereturn True  # 此时两个长度相等的字符串一定是字母异位词if __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')s = in_line[1].split(',')[0].strip()[1: -1]t = in_line[2].strip()[1: -1]print(obj.isAnagram(s, t))except EOFError:break

438. 找到字符串中所有字母异位词

1、这道题目要在长序列中找短序列的字母异位词，滑动窗口的长度首先要等于短序列的长度（定长），才能进一步比较
2、字母异位词的比较通常有更便捷的思路一，即对两个序列排序后进行是否相等的判断，如果题目能够通过，那可以直接用这种方法
3、思路二滑动窗口+哈希表+matchKeys标记(刚好匹配或过匹配的键数量)，要准确理解“matchKeys标记(刚好匹配或过匹配的键数量)”为什么这样定义：
（1）在下面的具体代码中，可以发现遍历长序列和缩短滑窗时，为了提升效率，都只对存在于待匹配的哈希表中的元素才进行操作；
（2）同时，当滑窗右指针移动增加元素使得需要的字符数量变成负数，由刚好匹配变为过匹配时，matchKeys不减少；当滑窗左指针移动减少元素使得需要的字符数量变成零，由过匹配变为刚好匹配时，matchKeys不增加；
（3）最后，由于滑动窗口长度是恒定的，当matchKeys等于短序列长度时 一定满足 刚好匹配

from typing import List
'''
438. 找到字符串中所有字母异位词
题目描述：给定两个字符串s和 p，找到s中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:输入: s = "cbaebabacd", p = "abc"输出: [0,6]解释:起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
题眼：字母异位词 —— 判断 p 的排列之一是 s 的 子串
思路1：直接排序后比较字符串是否相等，与”49. 字母异位词分组“一样，这道题不建议这种方法
思路2：滑动窗口+哈希表+matchKeys标记(刚好匹配或过匹配的键数量)
注意：两个序列的滑动窗口，短序列转换为哈希表，在窗口滑动过程中更新matchKeys标记；滑动窗口的长度固定，意味着窗口长度超出时对left更新
'''class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:# 情况1、p字符串长度大于s字符串if len(s) < len(p):return []# 情况2、p字符串长度小于等于s字符串# # 思路1的做法：# result = []# needStr = ''.join(sorted(p))# for i in range(len(s) - len(p) + 1):  # 注意+1细节#     if ''.join(sorted(s[i: i + len(p)])) == needStr:#         result.append(i)# return result# 思路2：滑动窗口+哈希表+matchKeys标记(刚好匹配或过匹配的键数量)# 0、将p转换为哈希表：存储了需要匹配的字符种类及数量needHashTable = {}for ch in p:if ch not in needHashTable:needHashTable[ch] = 1else:needHashTable[ch] += 1# 定义滑动窗口操作的必要变量left, right = 0, 0matchKeys = 0  # 标记：与needHashTable刚好匹配或过匹配的键数量，即对应的元素数量 等于或大于对应的键值result = []while right < len(s):# 1、当移动right扩大窗口，进行哪些操作if s[right] in needHashTable:needHashTable[s[right]] -= 1  # 当需要的字符数量变成负数，由刚好匹配变为过匹配时，matchKeys不变if needHashTable[s[right]] == 0:  # 由欠匹配变为刚好匹配matchKeys += 1# 2、什么条件下，窗口应该暂停扩大，开始移动left缩小窗口while right - left + 1 > len(p):# 3、缩小窗口进行哪些操作if s[left] in needHashTable:needHashTable[s[left]] += 1  # 当需要的字符数量变成零，由过匹配变为刚好匹配时，matchKeys不变if needHashTable[s[left]] == 1:  # 由刚好匹配变为欠匹配matchKeys -= 1left += 1# 4、更新结果if matchKeys == len(needHashTable):  # 因为滑动窗口长度是恒定的，此时一定满足 刚好匹配result.append(left)right += 1return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('"')s1 = in_line[1]s2 = in_line[3]# print(s1, s2)print(obj.findAnagrams(s1, s2))except EOFError:break

567. 字符串的排列

这道题目与“438. 找到字符串中所有字母异位词”是一个题意，排列与字母异位词是完全相同的意思

'''
567. 字符串的排列
题目描述：给你两个字符串s1和s2 ，写一个函数来判断 s2 是否包含 s1的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1:输入：s1 = "ab" s2 = "eidbaooo"输出：true解释：s2 包含 s1 的排列之一 ("ba").
题眼：判断 s1 的排列之一是 s2 的 子串
思路1：直接排序后比较字符串是否相等，与”49. 字母异位词分组“一样，这道题不建议这种方法
思路2：滑动窗口+哈希表+matchKeys标记(刚好匹配或过匹配的键数量)
注意：两个序列的滑动窗口，短序列转换为哈希表，在窗口滑动过程中更新matchKeys标记；滑动窗口的长度固定，意味着窗口长度超出时对left更新
'''class Solution:def checkInclusion(self, s1: str, s2: str) -> bool:# 跟“438. 找到字符串中所有字母异位词”是一个题意# 情况1、s1长度大于s2if len(s1) > len(s2):return False# 情况2、有两种方法# 方法一、直接排序字符串进行比较# sortedS1 = ''.join(sorted(s1))# for i in range(len(s2) - len(s1) + 1):#     if ''.join(sorted(s2[i: i + len(s1)])) == sortedS1:#         return True# return False# 方法二、滑动窗口+哈希表+matchKeys标记(刚好匹配或过匹配的键数量)# 0、将s1转换为哈希表：存储了需要匹配的字符种类及数量needHashTable = {}for ch in s1:if ch not in needHashTable:needHashTable[ch] = 1else:needHashTable[ch] += 1# 定义滑动窗口操作的必要变量left, right = 0, 0matchKeys = 0  # 标记：与needHashTable刚好匹配或过匹配的键数量，即对应的元素数量 等于或大于对应的键值while right < len(s2):# 1、当移动right扩大窗口，进行哪些操作if s2[right] in needHashTable:needHashTable[s2[right]] -= 1  # 当需要的字符数量变成负数，由刚好匹配变为过匹配时，matchKeys不变if needHashTable[s2[right]] == 0:  # 由欠匹配转为刚好匹配matchKeys += 1# 2、什么条件下，窗口应该暂停扩大，开始移动left缩小窗口while right - left + 1 > len(s1):# 3、缩小窗口进行哪些操作if s2[left] in needHashTable:needHashTable[s2[left]] += 1  # 当需要的字符数量变成零，由过匹配变为刚好匹配时，matchKeys不变if needHashTable[s2[left]] == 1:  # 由刚好匹配转为欠匹配matchKeys -= 1left += 1# 4、更新结果if matchKeys == len(needHashTable):  # 因为滑动窗口长度是恒定的，此时一定满足 刚好匹配return Trueright += 1return Falseif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('"')s1 = in_line[1]s2 = in_line[3]# print(s1, s2)print(obj.checkInclusion(s1, s2))except EOFError:break

49. 字母异位词分组

这道题目与本章总结的题型不是一个套路模板的解法，但有着字母异位词的字眼，与“438. 找到字符串中所有字母异位词”的思路一相同：直接将排序后的字符串作为键，将字符串数组转换为字典哈希表，直接返回list(字典的值)

from typing import List
'''
49. 字母异位词分组
题目描述：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次
示例 1:输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
题眼：字母异位词  分组
思路：直接将排序后的字符串作为键，将字符串数组转换为字典哈希表，直接返回list(字典的值)
'''class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:hashTable = {}for s in strs:key = ''.join(sorted(s))if key not in hashTable:hashTable[key] = [s]else:hashTable[key].append(s)return list(hashTable.values())if __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]strs = []if in_line != '':  # 整个输入为空if in_line == '""':  # 有一个空字符strs.append('')else:for i in in_line.split(','):strs.append(i.strip()[1: -1])print(obj.groupAnagrams(strs))except EOFError:break