0567：字符串的排列（★）

2016-07-20 约 270 字预计阅读 1 分钟次阅读

力扣第 567 题

题目

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

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

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

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

提示：

1 <= s1.length, s2.length <= 10⁴
s1 和 s2 仅包含小写字母

相似问题：

分析

类似于问题 0438 ，还更简单一点。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        m = len(s1)
        ct0 = Counter(s1)
        ct = defaultdict(int)
        valid = 0
        for j,c in enumerate(s2):
            ct[c] += 1
            if ct[c]==ct0[c]:
                valid += 1
            if j>=m:
                old = s2[j-m]
                if ct[old]==ct0[old]:
                    valid -= 1
                ct[old] -= 1
            if valid==len(ct0):
                return True
        return False

55 ms

目录

0567：字符串的排列（★）

题目

分析

解答