leetcode回顾——字符串的排列

LeetCode

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

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

示例1:

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

示例2:

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

初期解题思路

滑动窗口+字符串排序+list比较——>超时

要求s1的任意排序是否是s2的子串，如果对s1的排序结果搜索的话，那百分之百是会超时的，这个时候，就要从s2入手了，因此s1可以任意排序，那么，在s2上设置一个长度为s1的滑动窗口，在s2上滑动，将滑动窗口内的字符串进行ascii排序，同时对s1采取同样的操作，然后比较排序后两个list是否相等，如果不相等，那么窗口右移一个字母

python 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        len_s1 = len(s1)
        s_1 = list(s1).sort()
        l = 0
        while l < len(s2):
            r = l + len_s1
            tmp = list(s2[l: r])
            tmp.sort()
            if tmp == s_1:
                return True
            else:
                l += 1
        return False

正确解题思路

滑动窗口+字符出现次数hash表

最开始的思路只对了一半。也就是滑动窗口，但是，耗时在了排序，其实，并不用去管字母的顺序，只需要比较s1中各个字母出现的次数与s2的滑动窗口内各个字母出现的次数即可，其时间复杂度就是O(N - M)

python 代码

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
class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        len_s1 = len(s1)
        s_1 = [0 for i in range(26)]
        s_2 = [0 for i in range(26)]
        for i in range(len(s1)):
            s_1[ord(s1[i]) - ord('a')] += 1
        l = 0
        r = l
        while l <= len(s2) - len_s1:
            if r == len(s2):
                break
            if r >= len_s1:
                l += 1
                s_2[ord(s2[l - 1]) - ord('a')] -= 1
            s_2[ord(s2[r]) - ord('a')] += 1
            r += 1
            if s_2 == s_1:
                return True
        return False