567. 字符串的排列

问题

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

示例1:

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

示例2:

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

注意：

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

解法

题目乍一看似乎没什么好办法，暴力遍历总是行得通。但是时间复杂度嘛，嘿嘿。

接下来深挖一下题目，既然是判断 $s2$ 是否包含 $s1$ ，那么我们总是可以排除一些明显不满足条件的地方：

$s1$ 或 $s2$ 为空
$s2$ 的长度小于 $s1$

接下来，我们假设 $s2$ 中有 $s1$ 的排列 $a$ ，那么这个排列 $a$ 的长度肯定是 $s1$ 的长度 $length$ ，实际上就是判断这两个字符串不管字母顺序是否相同，
判断两个字符串是否相同可以用一个长度为26的数组，遍历第一个，将字母出现的次数记下来，然后遍历另一个字符串将数组中字母出现的次数减小一，当次数减小到-1时，代表不相同，直接返回false。当遍历完仍然没有返回时，那么两个字符串肯定是相同的。
我们可以设置两个指针，一个起始指针 $start$ ，一个结束指针 $end$ ，并且有 $end = start +length - 1$ 。此时，从 $end$ 指针处往回判断。至于为什么从 $end$ 处往回走而不是从 $start$ 处往前走是因为，我们注意到这样一种情况，当 $end$ 处的字符在数组中出现次数已经减到0时， $end$ 处的字符必然不在排列 $a$ 中，此时， $start$ 可以直接跳到 $end+1$ 处，可以直接过滤掉部分字符。这样也就不用遍历必然失败的场景了。

代码

java实现

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        //  特殊情况直接跳出
        if (s1 == null || s2 == null || s2.length() < s1.length()) {
            return false;
        }
        // 初始化一个数组，将s1的字母出现次数保存在这个数组中去。
        int[] map = new int[26];
        int length = s1.length();
        //遍历s1放入map
        for (int i = 0; i < length; i++) {
            map[s1.charAt(i) - 'a']++;
        }
        //遍历s2，此时注意到这样一个情况，如果s2包含s1，那么s2子串的长度必然等于s1，因此，可以设置两个指针。
        int start = 0, end = length - 1;
        while (end < s2.length()) {
            // 这里是一个注意点，需要注意不能直接用map处理，否则会导致第一次false后，后面的判断全是false
            int[] temp = map.clone();
            while (end >= start) {
                if (temp[s2.charAt(end) - 'a']-- == 0) {
                    break;
                }
                end--;
            }
            //上一层有两种跳出方式，一种break；一种是正确判断完了。需要区分一下。
            if (end < start) {
                //这种是正常判断完成了。直接返回true 
                return true;
            } else {
                //此时注意到这样一种情况，end处必然不能在s2子串中出现。那么start = end+1,end = start+length-1 可以跳过start与end之间的字符，因为这部分字符必然不满足条件。
                start = end + 1;
                end = start + length - 1;
            }
        }
        return false;
    }
}