题目
难度：★★★☆☆
类型：字符串
方法：滑动窗口
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False
注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
解答
首先我们回顾一下排列的定义。从一个数量为n的集合中抽取出来m个样本，按照任意顺序摆放起来，就可以称为原始集合的一个排列，如果m=n，那么这种排列就是原始集合的一个全排列。全排列有一个特性，即全排列中任意一种情况的样本，都可以在原始集合中找到，除了顺序之外略有差别，每个样本的出现次数与原始集合完全一致。
对于这道题目，为了找到长串s2中是否包含子串s1的全排列，只需要指定一个长度与段串s1一致的窗口，滑动窗口并统计窗口中各个元素出现次数是否与短串s1完全一致，如果一致，表明窗口中的子串与s1互为全排列。根据此可解决该问题。
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
c1 = {chr(i): 0 for i in range(97, 97+26)}
cur = c1.copy()
for a in s1:
c1[a] += 1
for i in range(len(s2)):
cur[s2[i]] += 1
if i >= len(s1):
cur[s2[i - len(s1)]] -= 1
if c1 == cur:
return True
return False
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
