567 字符串的排列（双指针、哈希表）

╰半橙微兮° 2022-08-31 10:00 173阅读 0赞

**1. 问题描述：**

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串 。

**示例 1：**

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

**示例 2：**

输入: s1= "ab" s2 = "eidboaoo"  
输出: False

**提示：**  
1 <= s1.length， s2.length <= 10 ^ 4  
s1 和 s2 仅包含小写字母  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/permutation-in-string

**2. 思路分析：**

这道题目属于经典的**双指针（滑动窗口）**题目，与力扣[438][]题本质上是一样的，438题求解的是满足条件的所有排列，这道题目求解的是否存在这样的排列，经典的做法是使用一个哈希表或者两个哈希表和结合双指针来维护长度为k的窗口，力扣的438题使用一个哈希表来维护窗口，这里使用两个哈希表S1，S2来维护长度为k窗口，其中k为字符串s1的长度，我们可以先将s1中字符出现的次数存储到S1中，在遍历字符串的时候维护长度为k的窗口（当发现当前的窗口的长度大于k之后那么需要删除掉左边窗口的字符），如何判断当前两个哈希表中对应字符出现的次数完全相同呢？我们可以声明一个变量count来维护哈希表S1中匹配的字符数量，但是如何在遍历字符的时候来更新这个变量呢？可以发现我们在维护长度为k的窗口的时候只会修改哈希表S2中对应窗口的左右边界的值，所以我们可以通过判断在添加和删除当前字符前后在两个哈希表中的关系来更新count，也即添加字符和删除字符的时候是从相等状态转为不相等状态还是从不相等状态状态转为相等状态来更新count，最后判断count是否等于了哈希表中匹配的字符数量，如果相等说明存在这样的排列返回True即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

**使用两个哈希表进行维护：**

class Solution:
        # 判断当前的字符在S1和S2中是否相等
        def check(self, c: str, S1: dict, S2: dict):
            if c in S1 and c in S2 and S1[c] == S2[c]:
                return True
            return False
    
        # 这里使用两个哈希表来维护
        def checkInclusion(self, s1: str, s2: str) -> bool:
            S1, S2 = dict(), dict()
            # 将s1中字符出现的次数存储到哈希表S1中
            for c in s1:
                if c not in S1:
                    S1[c] = 1
                else:
                    S1[c] += 1
            i, j = 0, 0
            count = 0
            while i < len(s2):
                c = s2[i]
                # 添加当前的s2[i]之前两个字符数量是相等的说明需要添加之后就不相等了所以需要减1
                if self.check(c, S1, S2): count -= 1
                # 更新S2中字符出现的次数
                if c not in S2:
                    S2[c] = 1
                else:
                    S2[c] += 1
                # 添加了当前字符之后发现相等了说明匹配的字符数量加1, 并且这上面和当前这个check函数的if判断只会进入其中一个或者都不进入, 对于窗口的左边界也是类似这样判断
                if self.check(c, S1, S2): count += 1
                c = s2[j]
                if i - j + 1 > len(s1):
                    if self.check(c, S1, S2): count -= 1
                    S2[c] -= 1
                    if self.check(s2[j], S1, S2): count += 1
                    j += 1
                # 匹配了S1中的所有字符
                if count == len(S1): return True
                i += 1
            return False

**修改一下438题的代码（使用一个哈希表进行维护）：**

from typing import List
     
    class Solution:
        def checkInclusion(self, s1: str, s2: str) -> List[int]:
            dic = dict()
            for c in s1:
                if c in dic:
                    dic[c] += 1
                else:
                    dic[c] = 1
            n = len(s2)
            i, j = 0, 0
            staisfy = 0
            res = list()
            # 其实每一次维护的是长度为k的窗口, k = len(p)
            while i < n:
                c = s2[i]
                # 当前需要匹配的字母c的次数减1
                if c in dic: dic[c] -= 1
                # 当前这个字母的次数满足要求
                if c in dic and dic[c] == 0:
                    staisfy += 1
                while i - j + 1 > len(s1):
                    # 删除最左边的字符如果删除的字符刚好是满足种类的数目那么satisfy需要减1
                    if s2[j] in dic and dic[s2[j]] == 0: staisfy -= 1
                    if s2[j] in dic:
                        dic[s2[j]] += 1
                    j += 1
                if staisfy == len(dic): return True
                i += 1
            return False

[438]: https://blog.csdn.net/qq_39445165/article/details/118364730
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/de06062404cc4145b384955c753fbd91.png