567. Permutation in String
給兩個字串s1、s2
會傳true如果s2包含s1的permutation
思路:
紀錄s1出現的每個字母次數
接著用two pointer去遍歷s2
扣掉相對應的字母次數
當字母次數出現負數
就移動前指標，直到該字母次數變成正數
去判斷前後指標相差的長度是不是等於s1的長度
是就回傳true
golang code :
func checkInclusion(s1 string, s2 string) bool {
rec, n := make([]int, 26), len(s1)
idx1, idx2 := 0, 0
for i := 0; i < n; i++ {
rec[int(s1[i]-'a')]++
}
for idx2 < len(s2) {
tmp := int(s2[idx2] - 'a')
rec[tmp]--
n--
if rec[tmp] < 0 {
for s2[idx2] != s2[idx1] {
rec[int(s2[idx1]-'a')]++
n++
idx1++
}
rec[tmp]++
n++
idx1++
} else if n == 0 {
return true
}
idx2++
}
if n == 0 {
return true
}
return false
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.212.211 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728181439.A.6B6.html