[算法训练]LeetCode 567: 字符串的排列

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
字符串的排列

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

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

示例1:

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


示例2:

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


注意:

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

Related Topics: 字符串 滑动窗口

思路

遍历s1所有的排列,判断是否为s2的子串,若是返回true,否则false

显而易见,仅仅是遍历字符串所有的排列,复杂度就已经是O(n!)了,阶乘级别,所以肯定行不通。

优化

借鉴[算法训练]LeetCode 3: 无重复字符的最长子串其中滑动窗口的思想

首先假设s1的长度 ≤ s2的长度,这样s1才有可能是s2的子串。

我们构造一个和s1长度相同的窗口,在s2中滑动。

那现在问题就是:如何快速判断s2窗口内的字符串是否为s1的排列组合之一

首先长度相同了,那只要两个字符串内的字符种类及其数量都一致,就肯定是排列之一了。

比如 aabbaa, 都是2个a,1个baabbaa是排列之一。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def checkInclusion(self, s1, s2):
slot1, slot2 = [0]*26, [0]*26
l1, l2 = len(s1), len(s2)
for c in s1:
slot1[ord(c)-97] += 1
for i in range(l2):
slot2[ord(s2[i])-97] += 1
if i >= l1:
slot2[ord(s2[i-l1])-97] -= 1
if slot1 == slot2:
return True
return False

如果大家有更好的解法,恳请不吝赐教,谢谢!

0%