【LeetCode】567. 字符串的排列

567. 字符串的排列

知识点：字符串；滑动窗口

题目描述

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的子串。

示例

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"

输出：true

解释：s2 包含 s1 的排列之一 ("ba")

示例 2:

输入：s1= "ab" s2 = "eidboaoo"

输出：false

。

解法一：滑动窗口

这其实也是滑动窗口的一道典型题目

注意题目中，排列的顺序不同可以算正确答案，所以只需要s1字典和当前窗口内的字典一模一样（含有的key相同，value也相同）即可了。

所以可以直接维持一个长度是s1的滑动窗口，并且统计窗口内的字典，然后和s1的字典比较即可了；

if两者一样，那直接返回即可

if两者不一样，那这个窗口移动，左、右都移动一个距离；

from collections import Counter, defaultdict

class Solution:

    def checkInclusion(self, s1: str, s2: str) -> bool:

        count_s1 = Counter(s1)  #s1中的字符数量

        start = 0

        count_s2 = Counter(s2[start:len(s1)-1])

        for i in range(len(s1)-1, len(s2)):

            count_s2[s2[i]] += 1

            if count_s1 == count_s2:

                return True

            else:

                count_s2[s2[start]] -= 1

            if count_s2[s2[start]] == 0:

                count_s2.pop(s2[start])

            start += 1

        return False

巴特西

【LeetCode】567. 字符串的排列

567. 字符串的排列

题目描述

示例

解法一：滑动窗口

最新文章

热门文章