...
| Code Block |
|---|
|
// 滑动窗口算法伪码框架
func slidingWindow(s string) {
// 用合适的数据结构记录窗口中的数据，根据具体场景变通
// 比如说，我想记录窗口中元素出现的次数，就用 map
// 如果我想记录窗口中的元素和，就可以只用一个 int
var window = ...
left, right := 0, 0 // 把索引左闭右开区间 [left, right) 称为一个「窗口」
for right < len(s) {
// c 是将移入窗口的字符
c := rune(s[right])
window[c]++
// 增大窗口
right++
// 进行窗口内数据的一系列更新
...
// *** debug 输出的位置 ***
// 注意在最终的解法代码中不要 print
// 因为 IO 操作很耗时，可能导致超时
fmt.Println("window: [",left,", ",right,")")
// ***********************
// 判断左侧窗口是否要收缩
for left < right && window needs shrink { //replace "window needs shrink" with actual condition
// d 是将移出窗口的字符
d := rune(s[left])
window[d]--
// 缩小窗口
left++
// 进行窗口内数据的一系列更新
...
}
}
} |
Minimum Window Substring 最小覆盖子串
https://leetcode.com/problems/minimum-window-substring/
| Code Block |
|---|
|
func minWindow(s string, t string) string {
T := toWindow(t)
initialResult := "x" + s
result := initialResult
var window [52]int
l, r := 0, 0
for r < len(s) {
windowAdd(&window, s[r])
r++
// fmt.Println("window: [",l,", ",r,")", s[l:r], "->", result)
for l < r && windowContains(window, T) {
if r - l < len(result) {
result = s[l:r]
}
windowRemove(&window, s[l])
l++
}
}
if result == initialResult {
return ""
}
return result
}
func toIndex(c byte) int {
if c >= 'A' && c <= 'Z' {
return int(c - 'A')
} else if c >= 'a' && c <= 'z' {
return 26 + int(c - 'a')
} else {
panic("Invalid character")
}
}
func toWindow(s string) (w [52]int) {
for _, r := range s {
w[toIndex(byte(r))]++
}
return
}
func windowAdd(window *[52]int, c byte) {
(*window)[toIndex(c)]++
}
func windowRemove(window *[52]int, c byte) {
(*window)[toIndex(c)]--
}
func windowContains(window1, window2 [52]int) bool { // window1 contains all window2
for i := range window1 {
if window1[i] < window2[i] {
return false
}
}
return true
} |