567.字符串的排列

【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中字符出现的顺序不重要。

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

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

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

AC代码

C++

class Solution {
public:
    bool checkInclusion(string& s1, string& s2) {
        if (s1.size() > s2.size()) {
            return false;
        }
        vector<int> 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 False
        cnt1 = [0 for _ in range(26)]
        cnt2 = [0 for _ in range(26)]
        for c in s1:
            cnt1[ord(c) - ord('a')] += 1
        for i in range(len(s1)):
            cnt2[ord(s2[i]) - ord('a')] += 1
        if cnt1 == cnt2:
            return True
        for i in range(len(s1), len(s2)):
            cnt2[ord(s2[i]) - ord('a')] += 1
            cnt2[ord(s2[i - len(s1)]) - ord('a')] -= 1
            if cnt1 == cnt2:
                return True
        return False

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