0567. 字符串的排列

0567. 字符串的排列 #

  • 标签:哈希表、双指针、字符串、滑动窗口
  • 难度:中等

题目大意 #

给定两个字符串 s1s2

要求:判断 s2 是否包含 s1 的排列。如果包含,返回 True;否则,返回 False

解题思路 #

题目要求判断 s2 是否包含 s1 的排列,则 s2 的子串长度等于 s1 的长度。我们可以维护一个长度为字符串 s1 长度的固定长度的滑动窗口。

先统计出字符串 s1 中各个字符的数量,我们用 s1_count 来表示。这个过程可以用字典、数组来实现,也可以直接用 collections.Counter() 实现。再统计 s2 对应窗口内的字符数量 window_count,然后不断向右滑动,然后进行比较。如果对应字符数量相同,则返回 True,否则继续滑动。直到末尾时,返回 False。整个解题步骤具体如下:

  1. s1_count 用来统计 s1 中各个字符数量。window_count 用来维护窗口中 s2 对应子串的各个字符数量。window_size 表示固定窗口的长度,值为 len(s1)
  2. 先统计出 s1 中各个字符数量。
  3. leftright 都指向序列的第一个元素,即:left = 0right = 0
  4. 向右移动 right,先将 len(s1) 个元素填入窗口中。
  5. 当窗口元素个数为 window_size 时,即:right - left + 1 >= window_size 时,判断窗口内各个字符数量 window_count 是否等于 s1 中各个字符数量 s1_count
    1. 如果等于,直接返回 True
    2. 如果不等于,则向右移动 left,从而缩小窗口长度,即 left += 1,使得窗口大小始终保持为 window_size
  6. 重复 4 ~ 5 步,直到 right 到达数组末尾。返回 False

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
import collections

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        left, right = 0, 0
        s1_count = collections.Counter(s1)
        window_count = collections.Counter()
        window_size = len(s1)

        while right < len(s2):
            window_count[s2[right]] += 1

            if right - left + 1 >= window_size:
                if window_count == s1_count:
                    return True
                window_count[s2[left]] -= 1
                if window_count[s2[left]] == 0:
                    del window_count[s2[left]]
                left += 1
            right += 1
        return False
本站总访问量  次  |  您是本站第  位访问者