题目

难度：★★★☆☆
类型：字符串
方法：滑动窗口

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定两个字符串 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解决方案，请移步力扣中等题解析