173 - 567 字符串的排列 027

题目

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

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

示例2:

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

注意：

1. 输入的字符串只包含小写字母

2. 两个字符串的长度都在 [1, 10,000] 之间

解答

https://leetcode-cn.com/problems/permutation-in-string/solution/shuang-zhi-zhen-shuang-ha-xi-by-88daxiong/

https://leetcode.com/problems/permutation-in-string/discuss/102588/Java-Solution-Sliding-Window

• 如果s2要包含s1的排列，那么s1中所有的字母，都得出现在s2里面

  因此可以用一个数组来记录出现的频率

• 可以用一个窗口，即截取s2的一部分，

class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        def getHash(s): # 拿到哈希
            hashTable = dict()
            for c in s:
                if c not in hashTable:
                    hashTable[c] = 0
                hashTable[c] += 1
            return hashTable

        lenS1 = len(s1)
        lenS2 = len(s2)
        lenDiff = lenS2 - lenS1

        if lenDiff < 0:
            return False

        head, tail = 0, lenS1 - 1
        hashS1 = getHash(s1)
        hashS2 = getHash(s2[head: tail + 1])
        while tail < lenS2:
            if hashS1 == hashS2:
                return True
            tail += 1
            if tail == lenS2:
                break
            if s2[tail] not in hashS1:
                if tail + 1 + lenS1 >= lenS2:
                    break
                else:
                    head = tail + 1
                    tail = head + lenS1 - 1
                    hashS2 = getHash(s2[head: tail + 1])
            else:
                if s2[tail] not in hashS2:
                    hashS2[s2[tail]] = 0
                hashS2[s2[tail]] += 1
                hashS2[s2[head]] -= 1
                if hashS2[s2[head]] == 0: #这里需要注意的是，如果这里没有了这个数，则需要删除这个键值
                    del hashS2[s2[head]]
                head += 1

        return False

Runtime: 56 ms, faster than 95.90% of Python3 online submissions for Permutation in String.

Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Permutation in String.

class Solution(object):
    def checkInclusion(self, s1, s2):
        A = [ord(x)-ord('a')for x in s1]
        B = [ord(x)-ord('a')for x in s2]
        target = [0]*26
        for x in A:
            target[x] += 1
        window = [0]*26
        for i, x in enumerate(B):
            window[x] += 1
            if i >= len(A):
                window[B[i-len(A)]] -= 1
            if window == target:
                return True
        return False

Runtime: 72 ms, faster than 69.88% of Python3 online submissions for Permutation in String.

Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Permutation in String.