朱晓峰

一只生之无趣死之乏味的丧家之犬

0%

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

Posted on Edited on In

题目

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的排列组合之一

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

比如 aab 和 baa， 都是2个a，1个b，aab是baa是排列之一。

代码

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

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