Leetcode 567 Permutation in String

发表于 |

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

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

示例2:
输入: s1= “ab” s2 = “eidboaoo”
输出: False

注意：

  1. 输入的字符串只包含小写字母
  2. 两个字符串的长度都在 [1, 10000] 之间

分析：

  1. 标准的滑动窗口解法，示例都太简单，我在这里给出一个例子帮助理解,s1 = ‘abca’,s2 = ‘baabc’
  2. 我们有很多方法判断两个等长的字符串是不是所含字母个数也相同，如collections模块中的Counter函数，如构造一个长度为26的数组，分别记录对应英文字母的个数，这里我们不妨就选后者来进行存储
  3. 对于例子来说:
    1. 初始化一个d1 = [2,1,1,0,…,0] 记录s1
    2. 初始化一个d2 = [2,2,0,0,…,0] 记录s2中前len(s1)个元素，此时窗口笼罩着'baab'
    3. 判断d1 == d2，因为长度为26，且字符串长度不超过10000，故滑动一次只需要比较26次，共滑动len(s2)-len(s1)+1次，所以显然不会超时
    4. 开始滑动，此时窗口笼罩着'aabc'，d2中b减少1，c增加1，再次比较，依此类推，直至遍历结束

思路：

  1. 用ord()函数将字符串转换成asc码
  2. 防止index error，先判断一下len(s2) < len(s1)？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s2) < len(s1): return False
        d1 = [0] * 26
        d2 = [0] * 26
        
        def helper(s):
            return ord(s) - ord('a')
        # 初始化d1,d2
        for i in range(len(s1)):
            d1[helper(s1[i])] += 1
            d2[helper(s2[i])] += 1
        if d1 == d2: return True

        # 开始滑动
        for i in range(len(s2)-len(s1)):
            d2[helper(s2[i])] -= 1
            d2[helper(s2[i+len(s1)])] += 1
            if d1 == d2: return True
        return False

102 / 102 test cases passed.
difficulty: medium
Runtime: 60 ms,beats 99%