滑动窗口方法解leetcode之438-找到字符串中所有字母异位词

题目描述:

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

输入: s = “abab”, p = “ab”

输出: [0,1,2]

解释: 起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。

起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。

起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

解题思路:

因为字符顺序可以不同，但是在相同长度范围内，字符长度与出现的次数一定要一样
滑动窗口 + 字典/ 数组

golang示例代码

 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
44
45
46
47
48
49


func findAnagrams(s string, p string) []int {
    totals := make([]int, 0)
    if len(p) > len(s) {
        return totals
    }
	// 先记录各字符出现的次数
    dict := map[byte]int{}
    for i := range p {
        dict[p[i]] += 1
    }
    left := 0
    right := 0
    count := map[byte]int{}
    for left <= len(s) && right <= len(s) {
		// 右指针走至同p的长度，同时更新计算的字典count
        for right < len(p) {
            count[s[right]] += 1
            right++
        }
		// 到这里，说明窗口大小 == 待比对字符，计算两字典值是否一致
        if isEqual(dict, count) {
           totals = append(totals, left)
        }
        if left < len(s) && right < len(s) {
			// 右边进来的加入字典内
            count[s[right]] += 1
			// 左边的出字典
            count[s[left]]  -= 1
            if count[s[left]] == 0 {
                delete(count, s[left])
            }
        }
		// 左右窗口同时移动
        left  += 1
        right += 1
    }
    return totals
}


func isEqual(d1, d2 map[byte]int) bool {
    for k, v := range d1 {
        value, ok := d2[k]
        if value != v || !ok {
            return false
        }
    }
    return true
}

因为题目限定字符为小写英文字母，所以可以用数组方法，效率提升好多。上面map费时40ms，下面的4ms，提升10倍…

 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


func findAnagrams(s string, p string) []int {
   totals := make([]int, 0)
    if len(p) > len(s) {
        return totals
    }
    count1 := [26]int{}
    count2 := [26]int{}
    for i := range p {
        index := p[i] - 'a'
        count1[index] += 1
    }
    left := 0
    right := 0
    for left <= len(s) && right <= len(s) {
        for right < len(p) {
            index := s[right] - 'a'
            count2[index] += 1
            right++
        }
        if count1 == count2 {
            totals = append(totals, left)
        }
        if left < len(s) && right < len(s) {
            count2[s[right] - 'a'] += 1
            count2[s[left] - 'a']  -= 1
        }
        left += 1
        right += 1
    }
    return totals
}

文章目录