LeetCode 567. 字符串的排列

 567. 字符串的排列

难度中等773

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"

输出：true

解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo"

输出：false

提示：

• 1 <= s1.length, s2.length <= 104
• s1 和 s2 仅包含小写字母

思路：滑动窗口

时间复杂度：O(m+n)，而题目说明进包含小写字母，长度为26，所以近似O(1)

空间复杂度：O(m+n)，而题目说明进包含小写字母，长度为26，所以近似O(1)

funccheckInclusion(s1string, s2string) bool {
length1, length2 :=len(s1), len(s2)
iflength1>length2 {
returnfalse    }
vararr1, arr2 [26]int// 先统计s1中出现的“字符+次数”，顺便初始化s2的滑动窗口arr2fori :=0; i<length1; i++ {
arr1[s1[i]-'a']++arr2[s2[i]-'a']++// arr2表示长度为length1的滑动窗口    }
// 若在s2中的前length1长度就包含了s1的排列，直接返回trueifarr1==arr2 {
returntrue    }
// 继续遍历s2后续部分的子串fori :=length1; i<length2; i++ {
arr2[s2[i]-'a']++// 右边界扩大一位arr2[s2[i-length1]-'a']--// 左边界缩小一位ifarr1==arr2 {
returntrue        }
    }
returnfalse}