567.字符串中的排列

滑动窗口

567.字符串中的排列

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

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

示例 1：

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

输入：s1= "ab" s2 = "eidboaoo"
输出：false

如果s2的某一子串是s1的排列，则返回true，否则返回false。首先要满足这个条件，s2的长度一定要大于等于s1的长度，即：

if (s1.length() > s2.length()) {
    return false;
}

字符串中保存的是小写字母，可以用一个大小为26的数组来保存s1中字母出现的次数，因为满足条件的s2的子串长度一定等于s1的长度，所以在s2中维护一个长度为s1的长度的滑动窗口，同样用一个数组来表示该窗口中字母出现的次数：

int[] arr1 = new int[26];
for (int i = 0; i < s1.length(); i++) {
    arr1[s1.charAt(i) - 'a']++;
}
int[] arr2 = new int[26];
for (int i = 0; i < s1.length(); i++) {
    arr2[s2.charAt(i) - 'a']++;
}

因为s1是排列，所以只要窗口中的元素全部在s1中出现，则说明该窗口是s1的一个排列，这样我们就只需要比较每次滑动窗口后两个数组是否相同了，维护滑动窗口数组即每次去掉最左边元素的同时将最右边即将进入窗口元素加进来，通俗点讲就是把要出窗口的元素在数组中-1，要加进来的元素在数组中+1。
整体代码如下：

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) { //如果s1的长度大于s2的长度，则条件不可能成立，直接返回
            return false;
        }
        int[] arr1 = new int[26];
        for (int i = 0; i < s1.length(); i++) { //将s1保存在一个大小为26的数组中
            arr1[s1.charAt(i) - 'a']++;
        }
        int[] arr2 = new int[26];
        for (int i = 0; i < s1.length(); i++) { //创建窗口，窗口长度应该为s1的长度
            arr2[s2.charAt(i) - 'a']++;
        }
        if (equals(arr1, arr2)) { //判断两个数组是否相同，相同则返回true
            return true;
        }
        for (int i = 0; i < s2.length() - s1.length(); i++) { //维护滑动窗口
            arr2[s2.charAt(i) - 'a']--;   //去掉出窗口的元素
            arr2[s2.charAt(i + s1.length()) - 'a']++;  //加入进入窗口的元素
            if (equals(arr1, arr2)) {  //判断两个数组是否相同，相同则返回true
                return true;
            }
        }
        return false; //遍历完s2后还没有找到符合条件的子串则返回false
    }

    boolean equals(int[] arr1,int[] arr2) { //判断两个数组是否相等
        for (int i = 0; i < 26; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }
}

原文：https://leetcode.cn/problems/permutation-in-string/solution/by-nice-hermann9a2-dmbm/