LeetCode 567. Permutation in String

Posted on | In |
Words count in article: 171 | Reading time ≈ 1

题目

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:

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

Example 2:

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

Note:

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

思路

滑动窗口+双指针。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        counter1 = collections.Counter(s1)
        counter2 = collections.Counter()
        l, r = 0, 0
        while r < len(s2):
            counter2[s2[r]] += 1
            if r-l+1 == len(s1):
                if counter2 == counter1:
                    return True
                counter2[s2[l]] -= 1
                if counter2[s2[l]] == 0:
                    del counter2[s2[l]]
                l += 1
            r += 1
        return False