0567.md

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

Constraints:

The input strings only contain lower case letters. The length of both given strings is in range [1, 10,000].

思路

key: two pointer

代码

func checkInclusion(s1 string, s2 string) bool {
    if len(s1) > len(s2) {
        return false
    }
    cache := make(map[byte]int, len(s1))
    for i := 0; i < len(s1); i++ {
        cache[s1[i]]++
    }
    begin := 0
    for i := 0; i < len(s2); i++ {
        _, ok := cache[s2[i]]
        if !ok {
            for j := begin; j < i; j++{
                cache[s2[j]]++
            }
            begin = i+1
            continue
        }
        if cache[s2[i]] == 0 {
            for j := begin; j < i; j++ {
                cache[s2[j]]++
                if s2[j] == s2[i] {
                    begin = j+1
                    break
                }
            }
        }
        cache[s2[i]]--
        if i - begin + 1 == len(s1) {
            return true
        }
    }
    return false
}