Leetcode - Permutation in String

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
}

• 相关文章
• 全局相关文章