字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。注意：

  1. 输入的字符串只包含小写字母
  2. 两个字符串的长度都在 [1, 10,000] 之间
  • code 
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
 
func checkInclusion(s1 string, s2 string) bool {
    if len(s1) > len(s2) { // 长度比较
        return false
    }
    v1 := sumstring(s1)
    i:=len(s1)
    v2 := sumstring(s2[:i])
    for i <= len(s2) {
        if i > len(s1){
            v2 += int(s2[i-1]) - int(s2[i-len(s1)-1])
        }
        if v1 == v2 { // 在字符值相等的情况下才去判断是否是排列
            if p(s1, s2[i-len(s1):i]) {
                return true
            }
        }
        i++
    }
    return false
}

func sumstring(s string) int { // 计算string值
    sum := 0
    for i := range s {
        sum += int(s[i])
    }
    return sum
}

func p(b1, b2 string) bool {  // 判断是否是排列，也可以用排序算法降低空间复杂度
    m1 := make(map[byte]int)
    m2 := make(map[byte]int)
    for i := range b1 {
        m1[b1[i]] += 1
        m2[b2[i]] += 1
    }
    for b, i := range m1 {
        if m2[b] != i {
            return false
        }
    }
    return true
}