# Leetcode - Permutation in String

violet posted @ May 19, 2020 05:30:07 AM in 算法 with tags Algorithm Golang SlidingWindow hash , 380 阅读

https://leetcode.com/problems/permutation-in-string/

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1:

Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

func checkInclusion(s1 string, s2 string) bool {
hash1 := map[byte]int{}
for i := 0; i < len(s1); i++ {
hash1[s1[i]]++
}
count := 0
i := 0
hash2 := map[byte]int{}
for i < len(s2) {
if _, ok := hash1[s2[i]]; !ok {
if count > 0 {
count--
}
i++
continue
}
if i >= len(s2) {
break
}
for j := i + count; j < len(s2) && count < len(s1); j++ {
count++
hash2[s2[j]]++
}
found := true
for key, val := range hash1 {
if v, ok := hash2[key]; !ok || v != val {
found = false
}
}

if found {
return true
}
hash2[s2[i]]--
count--
if hash2[s2[i]] <= 0 {
delete(hash2, s2[i])
}
i++
}
return false
}

(输入验证码)
or Ctrl+Enter