上一篇: 算法随笔_10: 供暖器-CSDN博客

题目描述如下:

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的 排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

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

算法思路:

我们设s1的长度为s1_len。通常能想到的算法就是在s2里逐个判断以每个字符为起始点，长度为s1_len的子串，是否是s1的一个排列。

至于如何判断是否是s1的一个排列？我们可以这样做:

1. 拷贝s1字符串到s1_cp数组中。

2. 对于子串sub_str，访问逐个字符，同时每访问一个字符就判断这个字符是否存在于s1_cp中。如果存在，在s1_cp中删除这个字符。全部迭代完之后，如果s1_cp为空，则表示子串sub_str是s1的一个排列。如果不存在这个字符，或者s1_cp不为空，则表示不是一个排列。

我们看到上面这个算法时间复杂度还是挺高的，不是一个较好的算法。接下来我们看看如何进行优化。

我们发现上面步骤2中每存在一个字符就删除一个字符，这是不是就相当于我们数了一下这个字符的个数？当每个字符的个数和s1中每个字符的个数一样的时候，我们就找到了s1的一个排列。

我们基于这个思想，就可以优化上面那个算法了。优化后的步骤如下:

1. 我们提前数好s1的每个字符个数，把它存在一个字典中s1_dct。

2. 迭代子串sub_str一遍，记录每个字符的个数，最后和s1_dct进行比较，判断是否是s1的一个排列。

3.对于s2的每个子串重复步骤2。直至找出答案。

我们还可以继续优化上面的算法。我们发现步骤3里把每个子串都重复了步骤2。其实这是不必要的。由于子串的长度是固定的，这其实类似滑动窗口的机制。窗口的长度就是s1的长度。我们发现每往右滑动一格，前一次的子串的计算结果(即，每个字符的个数)其实可以复用的。只是在计算结果里，相应的减去离开窗口的那个字符一次，并且加上进入窗口的那个字符一次。这样一来整个的算法就很高效了。