【LetMeFly】567.字符串的排列

力扣题目链接：https://leetcode.cn/problems/permutation-in-string/

给你两个字符串 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 <= 104
• s1 和 s2 仅包含小写字母

方法一：滑动窗口 / 双指针

题目问的是“s1的排列之一是否为s2的子串”，因此s1中字符出现的顺序不重要。

我们只需要统计s1s1s1中每个字母分别出现了几次，然后在s2中，判断是否存在相同长度的字符串，其中字母的出现次数和s1完全相同。

因此，首先统计s2中前len(s1)个字母是什么，接着不断加上这个区间后面的字符，减去这个区间前面的字符。中途遇到两字符串中字母相同的情况的话，返回true即可

• 时间复杂度O((len(s1)+len(s2))×C)O((len(s1) + len(s2)) \times C)O((len(s1)+len(s2))×C)，其中C=26C = 26C=26
• 空间复杂度O(C)O(C)O(C)

AC代码

C++

class Solution {
public:bool checkInclusion(string& s1, string& s2) {if (s1.size() > s2.size()) {return false;}vector cnt1(26), cnt2(26);for (char c : s1) {cnt1[c - 'a']++;}for (int i = 0; i < s1.size(); i++) {cnt2[s2[i] - 'a']++;}if (cnt1 == cnt2) {return true;}for (int i = s1.size(); i < s2.size(); i++) {cnt2[s2[i] - 'a']++;cnt2[s2[i - s1.size()] - 'a']--;if (cnt1 == cnt2) {return true;}}return false;}
};

Python

class Solution:def checkInclusion(self, s1: str, s2: str) -> bool:if len(s1) > len(s2):return Falsecnt1 = [0 for _ in range(26)]cnt2 = [0 for _ in range(26)]for c in s1:cnt1[ord(c) - ord('a')] += 1for i in range(len(s1)):cnt2[ord(s2[i]) - ord('a')] += 1if cnt1 == cnt2:return Truefor i in range(len(s1), len(s2)):cnt2[ord(s2[i]) - ord('a')] += 1cnt2[ord(s2[i - len(s1)]) - ord('a')] -= 1if cnt1 == cnt2:return Truereturn False

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/129636871