567. 字符串的排列
给你两个字符串 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 仅包含小写字母
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
滑动窗口的题目，看了一样别人提交的示例，发现了不同的收缩窗口的时机，然后就是别人的代码就要简洁很多了。
func checkInclusion(s1 string, s2 string) bool {
needs := make(map[byte]int)
needsCount := make(map[byte]int)
overCount := 0
count2 := len(s2)
s1Bytes := []byte(s1)
s2Bytes := []byte(s2)
left, right := 0, 0
// initial the needs map from s1 string
for i := 0; i < len(s1); i++{
char := s1Bytes[i]
needs[char]++
}
/**
左指针移动有两种情况：
1. 遇到s1中不存在的字符，导致截断
2. 遇到s1中存在但是，超出了需要的数目，导致的冗余
*/
for right < count2{
// 当遇到不在s1中的字符时，直接从下一个字符开始
char := s2Bytes[right]
if _, exist := needs[char]; !exist{
right++
left = right
needsCount = make(map[byte]int)
overCount = 0
continue
}
needsCount[char]++
right++
charCount := needsCount[char]
target := needs[char]
if charCount == target{
overCount++
// s1的字符都在s2中找到了
if overCount == len(needs){
return true
}
}else if charCount > target{
for {
charLeft := s2Bytes[left]
left++
// 不能一直减！调换一下位置，这里是指在未减之前是刚好的
if needsCount[charLeft] == needs[charLeft]{
overCount--
}
needsCount[charLeft]--
if needsCount[charLeft] == needs[charLeft]{
break
}
}
}
}
return false
}
去掉一些冗余的变量声明
func checkInclusion(s1 string, s2 string) bool {
needs := make(map[uint8]int)
window := make(map[uint8]int)
overCount := 0
count2 := len(s2)
left, right := 0, 0
// initial the needs map from s1 string
for i := 0; i < len(s1); i++{
needs[s1[i]]++
}
/**
左指针移动有两种情况：
1. 遇到s1中不存在的字符，导致截断
2. 遇到s1中存在但是，超出了需要的数目，导致的冗余
*/
for right < count2{
// 当遇到不在s1中的字符时，直接从下一个字符开始
char := s2[right]
if _, exist := needs[char]; !exist{
right++
left = right
window = make(map[byte]int)
overCount = 0
continue
}
window[char]++
right++
charCount := window[char]
target := needs[char]
if charCount == target{
overCount++
// s1的字符都在s2中找到了
if overCount == len(needs){
return true
}
}else if charCount > target{
for {
charLeft := s2[left]
left++
// 不能一直减！调换一下位置，这里是指在未减之前是刚好的
if window[charLeft] == needs[charLeft]{
overCount--
}
window[charLeft]--
if window[charLeft] == needs[charLeft]{
break
}
}
}
}
return false
}
别人的12ms 的范例
package main
func main(){
s1 := "ab"
s2 := "bdandjkaskdnljab"
checkInclusionExample(s1, s2)
}
// 人家字符串用下标访问的很顺畅。。。。
// 看来不是数据类型的问题，而是 map 的声明问题
// 如果希望建立字符到整形的映射，那么注意使用 uint8 作为接受类型！
func checkInclusionExample(s1 string, s2 string) bool {
window := make(map[uint8]int)
need := make(map[uint8]int)
var valid int
var left int
var right int
for i := 0; i < len(s1); i++ {
need[s1[i]]++
}
for right < len(s2) {
window[s2[right]]++
if window[s2[right]] == need[s2[right]] {
valid++
}
right++
// 这里缩小窗口的时机和我的还是不一样的
// right-left 等于 s1 的值时，实际上 [left, right] 要多出来一个元素
// 这就证明这个窗口范围内必然存在重复的值，开始缩小左侧的窗口
// 但是这个算法是如何避免非法字符的中间出现的问题呢？
/**
他这个意思就是只要存在解,那么就在移动左指针过程中使得当前窗口和目标字符相等，人家的收缩窗口的时机会放的晚一些，我的就早些了，然后对特殊情况进行处理了
*/
// 还有就是明显下面这个它只会跑一次的，
// 果然换成了if 一样正常跑
for right-left == len(s1) {
if valid == len(need) {
return true
}
if window[s2[left]] == need[s2[left]] {
valid--
}
window[s2[left]]--
left++
}
}
return false
}
