Python LeetCode-567. 字符串的排列（难度-中等）

1.题目

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

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

示例2：
输入: s1= "ab" s2 = "eidboaoo"
输出: False

注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间

2.分析

• 思路1：暴力，首先想到将s1构造成一个字典，然后以s1的长度为窗口，不断在s2上滑动构造字典，比较两个字典是否一致，如果一致就是True，可以这个暴力方法在构造字典方面速度太慢，妥妥的时间超时。
• 思路2：使用滑动窗口（上面的思路一致），不过这个写法省略了不断构造字典的问题，提高了速度。
• 思路3：目前市面上能看到最快最节约内存的方法，通过直接构造包含26个字母为key的字典，省去了在添加时候的判断，提高了效率。

3.解决

• 思路1：暴力解法，不断构造字典，看其中元素是否和target字典一致，嘻嘻，直接超时。

class Solution:
    def checkInclusion(self, s1: str, s2: str):
        if not s1 or not s2 or len(s1) > len(s2):
            return False

        target_dict = {}
        for i in s1:
            if i not in target_dict:
                target_dict[i] = 1
            else:
                target_dict[i] += 1
        print(target_dict)
        length_s1 = len(s1)
        j = 0
        while j + length_s1 <= len(s2):
            tmp_s2 = s2[j:j + length_s1]
            tmp_dict = {}
            for i in tmp_s2:
                if i in tmp_dict:
                    tmp_dict[i] = tmp_dict[i] + 1
                else:
                    tmp_dict[i] = 1
            if tmp_dict == target_dict:
                return True
            j += 1

        return False


if __name__ == '__main__':
    a = "ab"
    b = "eidbaooo"
    s = Solution()
    s.checkInclusion(a, b)

• 思路2：使用滑动窗口（上面的思路一致），不过这个写法省略了不断构造字典的问题，提高了速度

class Solution:

    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        s1_hash = {}
        s2_hash = {}
        for i in range(len(s1)):
            if s1[i] not in s1_hash.keys():
                s1_hash[s1[i]] = 1
            else:
                s1_hash[s1[i]] += 1

            if s2[i] not in s2_hash.keys():
                s2_hash[s2[i]] = 1
            else:
                s2_hash[s2[i]] += 1
        if s2_hash == s1_hash:
            return True
        else:
            left = 0
            right = len(s1)
            while right < len(s2):
                s2_hash[s2[left]] -= 1
                if s2_hash[s2[left]] == 0:
                    s2_hash.pop(s2[left])
                left += 1
                if s2[right] in s2_hash.keys():
                    s2_hash[s2[right]] += 1
                else:
                    s2_hash[s2[right]] = 1
                right += 1
                if s2_hash == s1_hash:
                    return True
        return False

• 思路3：leetcode目前最快最节约内存解法

class Solution:
    
    def checkInclusion(self, s1, s2):
        l1 = len(s1)
        l2 = len(s2)
        if s1 == s2:
            return True
        if l2 < l1:
            return False
        s = "abcdefghijklmnopqrstuvwxyz"
        dict1 = {}
        dict2 = {}

        for i in range(len(s)):
            dict1[s[i]] = 0
            dict2[s[i]] = 0

        for i in range(l1):
            dict1[s1[i]] += 1
            dict2[s2[i]] += 1

        if dict1 == dict2:
            return True

        for i in range(l2 - l1):
            dict2[s2[i]] -= 1
            dict2[s2[i + l1]] += 1
            if dict1 == dict2:
                return True

        return False


if __name__ == '__main__':
    s = Solution()
    s1 = "ab"
    s2 = "eidbaooo"
    print(s.checkInclusion(s1, s2))