567. 字符串的排列
給你兩個字符串 s1 和 s2 ，寫一個函數(shù)來判斷 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
滑動窗口的題目，看了一樣別人提交的示例，發(fā)現(xiàn)了不同的收縮窗口的時機，然后就是別人的代碼就要簡潔很多了。
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中不存在的字符，導(dǎo)致截斷
2. 遇到s1中存在但是，超出了需要的數(shù)目，導(dǎo)致的冗余
*/
for right < count2{
// 當(dāng)遇到不在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++
// 不能一直減！調(diào)換一下位置，這里是指在未減之前是剛好的
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中不存在的字符，導(dǎo)致截斷
2. 遇到s1中存在但是，超出了需要的數(shù)目，導(dǎo)致的冗余
*/
for right < count2{
// 當(dāng)遇到不在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++
// 不能一直減！調(diào)換一下位置，這里是指在未減之前是剛好的
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)
}
// 人家字符串用下標(biāo)訪問的很順暢。。。。
// 看來不是數(shù)據(jù)類型的問題，而是 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] 要多出來一個元素
// 這就證明這個窗口范圍內(nèi)必然存在重復(fù)的值，開始縮小左側(cè)的窗口
// 但是這個算法是如何避免非法字符的中間出現(xiàn)的問題呢？
/**
他這個意思就是只要存在解,那么就在移動左指針過程中使得當(dāng)前窗口和目標(biāo)字符相等，人家的收縮窗口的時機會放的晚一些，我的就早些了，然后對特殊情況進行處理了
*/
// 還有就是明顯下面這個它只會跑一次的，
// 果然換成了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
}
