题目描述

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

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

示例 1：

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

输入: s1= “ab” s2 = “eidboaoo”
输出: False

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题过程

解题思路

滑动窗口：统计s1每个字符串的个数。对于s2,设置一个滑动的窗口，同样统计窗口内每个字符串的个数。比较保存这些个数的数组，数组相等以为着成功找到这样的字符串。

以下为窗口滑动的过程：右边添加一个元素，则左边减少一个元素。

  for (int i = n; i < m; i++) {
        cnt2[s2.charAt(i) - 'a']++;
        cnt2[s2.charAt(i - n) - 'a']--;
        if (Arrays.equals(cnt1, cnt2)){
            return true;
        }
    }

完整代码：

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        if(n > m){
            return false;
        }
        char[] cnt1 = new char[26];
        char[] cnt2 = new char[26];

        for (int i = 0; i < n; i++) {
            cnt1[s1.charAt(i) - 'a']++;
            cnt2[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(cnt1,cnt2)){
            return true;
        }

        for (int i = n; i < m; i++) {
            cnt2[s2.charAt(i) - 'a']++;
            cnt2[s2.charAt(i - n) - 'a']--;
            if (Arrays.equals(cnt1, cnt2)){
                return true;
            }
        }
        return false;

    }
}