滑动窗口
LC 76. Minimum Window Substring 最小覆盖子串
https://leetcode.com/problems/minimum-window-substring/
func minWindow(s string, t string) string { expect := toNumArray(t) window := newNumArray() result := "" left, right := 0, 0 for right < len(s) { window.Add(s[right]) right++ for left < right && window.GreaterThanOrEqual(expect) { window.Remove(s[left]) result = shorter(result, s[left:right]) left++ } } return result } type NumArray []int func newNumArray() NumArray { return make(NumArray, 52) } func (arr NumArray) Add(c byte) { arr[toNum(c)]++ } func (arr NumArray) Remove(c byte) { arr[toNum(c)]-- } func (arr NumArray) GreaterThanOrEqual(another NumArray) bool { for i := range arr { if arr[i] < another[i] { return false } } return true } func toNumArray(s string) NumArray { arr := newNumArray() for i := range s { arr.Add(s[i]) } return arr } func toNum(c byte) int { if c >= 'a' && c <= 'z' { return int(c - 'a') } if c >= 'A' && c <= 'Z' { return int(c - 'A') + 26 } return -1 } func shorter(base, s string) string { if base == "" || len(s) < len(base) { return s } return base }
优化
利用统计「满足窗口条件的字符数」减少 GreaterThanOrEqual 判断的成本
func minWindow(s string, t string) string { expect := toNumArray(t) window := newNumArray() result := "" valid := 0 expectValid := 0 for _, c := range expect { if c > 0 { expectValid++ } } left, right := 0, 0 for right < len(s) { rx := toNum(s[right]) right++ if expect[rx] > 0 { window[rx]++ if window[rx] == expect[rx] { valid++ } } for left < right && valid == expectValid { lx := toNum(s[left]) if expect[lx] > 0 { if window[lx] == expect[lx] { valid-- } window[lx]-- } result = shorter(result, s[left:right]) left++ } } return result } type NumArray []int func newNumArray() NumArray { return make(NumArray, 52) } func toNumArray(s string) NumArray { arr := newNumArray() for i := range s { arr[toNum(s[i])]++ } return arr } func toNum(c byte) int { if c >= 'a' && c <= 'z' { return int(c - 'a') } if c >= 'A' && c <= 'Z' { return int(c - 'A') + 26 } return -1 } func shorter(base, s string) string { if base == "" || len(s) < len(base) { return s } return base }
LC 567. Permutation in String 字符串的排列
https://leetcode.com/problems/permutation-in-string/
func checkInclusion(s1 string, s2 string) bool { expect := toNumberMap(s1) window := newNumberMap() valid := 0 expectValid := 0 for _, c := range expect { if c > 0 { expectValid++ } } left, right := 0, 0 for right < len(s2) { rx := toNumber(s2[right]) if expect[rx] > 0 { window[rx] ++ if expect[rx] == window[rx] { valid++ } } right++ for left < right && valid == expectValid { lx := toNumber(s2[left]) if expect[lx] > 0 { if expect[lx] == window[lx] { valid-- } window[lx]-- } if right-left == len(s1) { return true } left++ } } return false } type NumberMap []int func newNumberMap() NumberMap { return make(NumberMap, 26) } func toNumberMap(s string) NumberMap { m := newNumberMap() for i := range s { m[toNumber(s[i])]++ } return m } func toNumber(c byte) int { return int(c - 'a') }
思路二：定长窗口
func checkInclusion(s1 string, s2 string) bool { expect := toNumberMap(s1) window := newNumberMap() valid := 0 expectValid := 0 for _, c := range expect { if c > 0 { expectValid++ } } left, right := 0, 0 for right < len(s2) { rx := toNumber(s2[right]) if expect[rx] > 0 { window[rx] ++ if expect[rx] == window[rx] { valid++ } } right++ if right - left == len(s1) { if valid == expectValid { return true } lx := toNumber(s2[left]) if expect[lx] > 0 { if expect[lx] == window[lx] { valid-- } window[lx]-- } left++ } } return false } type NumberMap []int func newNumberMap() NumberMap { return make(NumberMap, 26) } func toNumberMap(s string) NumberMap { m := newNumberMap() for i := range s { m[toNumber(s[i])]++ } return m } func toNumber(c byte) int { return int(c - 'a') }
LC 438. Find All Anagrams in a String 找到字符串中所有字母异位词
https://leetcode.com/problems/find-all-anagrams-in-a-string/
func findAnagrams(s string, p string) (result []int) { window := newNumMap() expect := toNumMap(p) valid := 0 expectValid := 0 for _, c := range expect { if c > 0 { expectValid++ } } left, right := 0, 0 for right < len(s) { if rx := idx(s[right]); expect[rx] > 0 { window[rx]++ if window[rx] == expect[rx] { valid++ } } right++ if right - left == len(p) { if valid == expectValid { result = append(result, left) } if lx := idx(s[left]); expect[lx] > 0 { if window[lx] == expect[lx] { valid-- } window[lx]-- } left++ } } return result } type NumMap []int func newNumMap() NumMap { return make(NumMap, 26) } func toNumMap(s string) NumMap { m := newNumMap() for i := range s { m[idx(s[i])]++ } return m } func idx(c byte) int { return int(c - 'a') }
LC 3. Longest Substring Without Repeating Characters 无重复字符的最长子串
https://leetcode.com/problems/longest-substring-without-repeating-characters/
func lengthOfLongestSubstring(s string) (result int) { window := make(map[byte]bool, 66) dup := false left, right := 0, 0 for right < len(s) { rc := s[right] if !window[rc] { window[rc] = true } else { dup = true } right++ if !dup { result = max(result, right-left) } for left < right && dup { lc := s[left] if lc == rc { dup = false } else { window[lc] = false } left++ } } return }
简化判断逻辑
（时间复杂度一样，但是似乎总执行时间没有上面引入 dup 做判断好 7ms vs 0ms - 当然不确定是否是 leetcode 的原因）
func lengthOfLongestSubstring(s string) (result int) { window := make(map[byte]int, 66) left, right := 0, 0 for right < len(s) { rc := s[right] window[rc]++ right++ for window[rc] > 1 { window[s[left]]-- left++ } result = max(result, right - left) } return }