字符串
算法技巧 - 滑动窗口
以下题目适用
# 最小覆盖子串 (opens new window)
给你一个字符串
s
、一个字符串t
。返回s
中涵盖t
所有字符的最小子串。如果s
中不存在涵盖t
所有字符的子串,则返回空字符串""
。
func minWindow(s string, t string) string { // 10 min 解决
need, window := map[byte]int{}, map[byte]int{}
left, right, valid, start := 0,0,0,0
length := math.MaxInt
// 记录满足字符串的频数
for i:= 0; i < len(t); i++ {
need[t[i]]++
}
for right < len(s) {
c := s[right]
right++ //扩大窗口
window[c]++
if window[c] == need[c]{ //相等时,说明有一个字符满足了条件
valid++
}
for valid == len(need) {
if right - left < length { // 判断一下,更新一下,最小子串的长度和起始值
start = left
length = right - left
}
d := s[left]
left++
if window[d] == need[d]{
valid--
}
window[d]--
}
}
if length == math.MaxInt{
return ""
} else {
end := start + length
return s[start:end]
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# 字符串的排列 (opens new window)
给你两个字符串
s1
和s2
,写一个函数来判断s2
是否包含s1
的排列。如果是,返回true
;否则,返回false
。换句话说,
s1
的排列之一是s2
的 子串 。
func checkInclusion(s1 string, s2 string) bool {
need, window := map[byte]int{}, map[byte]int{}
left, right, valid := 0,0,0
for i:=0; i<len(s1);i++{
need[s1[i]]++
}
for right < len(s2) {
c := s2[right]
right++
if _, ok := need[c];ok{
window[c]++
if window[c] == need[c] {
valid++
}
}
// todo PS:由于这道题中 [left, right) 其实维护的是一个定长的窗口,窗口大小为 len(s1)。因为定长窗口每次向前滑动时只会移出一个字符,所以可以把内层的 while 改成 if,效果是一样的。
for right - left >= len(s1) { // 判断左侧窗口是否要收缩:本题移动 left 缩小窗口的时机是窗口大小大于 len(s1) 时
if valid == len(need) { // 当发现 valid == len(need) 时,就说明窗口中就是一个合法的排列,所以立即返回 true。
return true
}
d := s2[left]
left++
if _, ok := need[d];ok{
if window[d] == need[d] {
valid--
}
window[d]--
}
}
}
return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 找到字符串中所有字母异位词 (opens new window)
给定两个字符串
s
和p
,找到s
中所有p
的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
func findAnagrams(s string, p string) []int {
need, window := map[byte]int{}, map[byte]int{}
left, right, valid := 0,0,0
var res []int
for i:=0;i<len(p);i++ {
need[p[i]]++
}
for right < len(s) {
c := s[right]
right++
if _,ok := need[c];ok {
window[c]++
if need[c] == window[c] {
valid++
}
}
for right - left >= len(p) {
if valid == len(need) { // 当窗口符合条件时,把起始索引加入 res
res = append(res, left)
}
d := s[left]
left++
if _,ok := need[d];ok {
if need[d] == window[d] {
valid--
}
window[d]--
}
}
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 无重复字符的最长子串 (opens new window)
给定一个字符串
s
,请你找出其中不含有重复字符的 最长子串 的长度。
func lengthOfLongestSubstring(s string) int {
window := map[byte]int{}
left, right, res := 0,0,0
for right < len(s) {
c := s[right]
right++
window[c]++
for window[c] > 1 {
d := s[left]
left++
window[d]--
}
res = max(res, right - left)
}
return res
}
func max(a,b int) int {
if a >= b {
return a
}else {
return b
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 反转字符串 (opens new window)
题目描述
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s
的形式给出。
不要给另外的数组分配额外的空间,你必须**原地 (opens new window)修改输入数组**、使用 O(1) 的额外空间解决这一问题。
示例 1:
输入:s = ["h","e","l","l","o"]
输出:["o","l","l","e","h"]
1
2
2
题解
func reverseString(s []byte) {
left := 0
right := len(s) - 1
for left < right{
s[left],s[right] = s[right], s[left]
left++
right--
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 验证回文串 (opens new window)
题目描述
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s
,如果它是 回文串 ,返回 true
;否则,返回 false
。
示例 1:
输入: s = "A man, a plan, a canal: Panama"
输出:true
解释:"amanaplanacanalpanama" 是回文串。
1
2
3
2
3
思路
所有字符转化成小写
过滤掉空格和标点这类字符
剩下的字符执行,两端向中心的双指针算法
题解
func isPalindrome(s string) bool {
if s == " " {
return true
}
var sgood string
for i := 0; i < len(s); i++ {
if isalnum(s[i]) {
sgood += string(s[i])
}
}
sgood = strings.ToLower(sgood)
left := 0
right := len(sgood) - 1
for left < right {
if sgood[left] != sgood[right] {
return false
}
left++
right--
}
return true
}
func isalnum(ch byte) bool {
return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 最长回文串 (opens new window)
题目
给你一个字符串 s
,找到 s
中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
1
2
3
2
3
题解
func longestPalindrome(s string) string {
var res string
for i := 0; i < len(s); i++ {
s1 := palindrome(s,i,i) // 以 s[i] 为中心的最长回文子串
s2 := palindrome(s,i,i + 1) // 以 s[i] 和 s[i+1] 为中心的最长回文子串
s1L := len(s1)
s2L := len(s2)
if len(res) < s1L {
res = s1
}
if len(res) < s2L {
res = s2
}
}
return res
}
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
// 如果输入相同的 l 和 r,就相当于寻找长度为奇数的回文串,如果输入相邻的 l 和 r,则相当于寻找长度为偶数的回文串。
func palindrome (s string, l int ,r int) string {
for l >= 0 && r < len(s) && s[l] == s[r] {
// 双指针,向两边展开
l--
r++
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s[l+1:r]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
编辑 (opens new window)
上次更新: 2023/03/03, 15:50:07