0567. 字符串的排列 #
- 标签:哈希表、双指针、字符串、滑动窗口
- 难度:中等
题目大意 #
给定两个字符串 s1
和 s2
。
要求:判断 s2
是否包含 s1
的排列。如果包含,返回 True
;否则,返回 False
。
解题思路 #
题目要求判断 s2
是否包含 s1
的排列,则 s2
的子串长度等于 s1
的长度。我们可以维护一个长度为字符串 s1
长度的固定长度的滑动窗口。
先统计出字符串 s1
中各个字符的数量,我们用 s1_count
来表示。这个过程可以用字典、数组来实现,也可以直接用 collections.Counter()
实现。再统计 s2
对应窗口内的字符数量 window_count
,然后不断向右滑动,然后进行比较。如果对应字符数量相同,则返回 True
,否则继续滑动。直到末尾时,返回 False
。整个解题步骤具体如下:
s1_count
用来统计s1
中各个字符数量。window_count
用来维护窗口中s2
对应子串的各个字符数量。window_size
表示固定窗口的长度,值为len(s1)
。- 先统计出
s1
中各个字符数量。 left
、right
都指向序列的第一个元素,即:left = 0
,right = 0
。- 向右移动
right
,先将len(s1)
个元素填入窗口中。 - 当窗口元素个数为
window_size
时,即:right - left + 1 >= window_size
时,判断窗口内各个字符数量window_count
是否等于s1
中各个字符数量s1_count
。- 如果等于,直接返回
True
。 - 如果不等于,则向右移动
left
,从而缩小窗口长度,即left += 1
,使得窗口大小始终保持为window_size
。
- 如果等于,直接返回
- 重复 4 ~ 5 步,直到
right
到达数组末尾。返回False
。
代码 #
|
|