难度: Medium
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
示例 1：
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例 2：
输入: s1= "ab" s2 = "eidboaoo" 输出: False
提示：
1 <= s1.length, s2.length <= 104s1 和 s2 仅包含小写字母注意：本题与主站 567 题相同： https://leetcode-cn.com/problems/permutation-in-string/
运行时间: 54 ms
内存: 16.0 MB
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
'''
仿照438的思路，先统计s1中各字符的数量
从前往后
'''
n, m = len(s1), len(s2)
s1_count = [0] * 26
s2_count = [0] * 26
for i in range(n):
s1_count[ord(s1[i]) - ord('a')] += 1
for right in range(m):
cur_right = ord(s2[right]) - ord('a')
s2_count[cur_right] += 1
if s2_count == s1_count:
return True
if right - n + 1 >= 0:
s2_count[ord(s2[right-n+1]) - ord('a')] -= 1
return False
这个题解采用了滑动窗口的方法来判断s2是否包含s1的某个变位词作为子串。首先，通过一个长度为26的数组s1_count来统计s1中每个字符的出现次数。数组的索引对应从'a'到'z'的每个字符。接着，使用同样的方式，通过另一个长度为26的数组s2_count来动态地在s2上维护一个长度为s1长度的滑动窗口的字符出现次数。随着窗口在s2上从左到右滑动，检查当前窗口内的字符分布是否与s1相同。如果在任何时刻两个数组相等，说明s2中存在一个子串是s1的变位词，返回True。如果遍历完s2后没有找到任何匹配，返回False。
时间复杂度: O(m)
空间复杂度: O(1)
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
n, m = len(s1), len(s2)
s1_count = [0] * 26 # 存储s1中每个字符的出现次数
s2_count = [0] * 26 # 存储当前s2的滑动窗口中的字符出现次数
for i in range(n):
s1_count[ord(s1[i]) - ord('a')] += 1 # 初始化s1的字符计数
for right in range(m):
cur_right = ord(s2[right]) - ord('a')
s2_count[cur_right] += 1 # 将当前字符加入滑动窗口
if s2_count == s1_count:
return True # 如果当前窗口的字符计数与s1相同，则找到一种排列
if right - n + 1 >= 0:
s2_count[ord(s2[right-n+1]) - ord('a')] -= 1 # 移动窗口，去除最左侧字符的计数
return False
在滑动窗口算法中，s2_count数组通过两种操作来保证其精确性：增加和减少字符计数。当窗口向右扩展时，新进入窗口的字符的计数会增加。当窗口左侧的字符移出窗口时，该字符的计数会相应减少。这样，s2_count数组始终精确地反映了当前窗口内各字符的频率。
实际上，比较两个数组是否相等确实需要遍历整个数组，因此这个操作的时间复杂度是O(26)，即O(1)。这里的O(1)表示常数时间复杂度，因为无论输入大小如何，比较的时间都是固定的，由于数组长度总是26，所以可以认为是常数时间。
如果s1的长度大于s2的长度，则不存在任何可能的窗口可以包含s1的排列，因为窗口的大小至少需要与s1的长度相等。在这种情况下，算法应该立即返回False。题解中虽未明确说明这一点，但在算法实现中，这种情况会自然地处理，因为窗口无法扩展到大于或等于s1长度，从而不会进入主要的比较逻辑。