字符串的排列

题目描述

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False

注意：

输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间

知识点

字符串

维持一个滑动窗口，通过计数比较两个串是否是排列关系。

class Solution:
    def judge(self, count1: list, count2: list) -> bool:
        for i in range(len(count1)):
            if count1[i]!=count2[i]:
                return False
        return True 
    
    def checkInclusion(self, s1: str, s2: str) -> bool:
        count1=[0 for i in range(ord('z')-ord('a')+1)]
        count2=[0 for i in range(ord('z')-ord('a')+1)]
        for c in s1:
            count1[ord(c)-ord('a')]+=1
        left=0
        right=0
        while right<len(s2):
            if s2[right] in s1:
                count2[ord(s2[right])-ord('a')]+=1
                if right-left+1==len(s1):
                    if self.judge(count1, count2)==True:
                        return True
                    else:
                        count2[ord(s2[left])-ord('a')]-=1
                        left+=1
                right+=1
            else:
                count2=[0 for i in range(ord('z')-ord('a')+1)]
                left=right+1
                right=right+1
        return False

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。