

LeetCode: 567. 字符串的排列

• LeetCode: 567. 字符串的排列
  • 1、题目描述
  • 2、解题思路

1、题目描述

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

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

示例1:

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

示例2:

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

注意：

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

2、解题思路

• 因为只有26个小写字母，只要s2中有一段连续的字符串每个字符出现的次数与s1相同即可

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections import Counter

        l1, l2 = len(s1), len(s2)

        if l2 < l1:
            return False

        s1_c = [0] * 26
        for char, num in Counter(s1).items():
            s1_c[ord(char) - ord('a')] = num

        s2_windows = [0] * 26
        for char, num in Counter(s2[:l1]).items():
            s2_windows[ord(char) - ord('a')] = num

        if s1_c == s2_windows:
            return True
        for i in range(l1, l2):
            s2_windows[ord(s2[i]) - ord('a')] += 1
            s2_windows[ord(s2[i - l1]) - ord('a')] -= 1
            if s1_c == s2_windows:
                return True

        return False