每日一题-Day32-字符串的排列

题目

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

示例：

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

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

解题思路

滑动窗口：与常规的滑动窗口题目不同，该题目要求判断s2是否包含s1的排列，所以我们只需要判断滑动窗口内字母的个数是否相同即可

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        int[] temp1 = new int[26];
        int[] temp2 = new int[26];
        if (n > m) {
            return false;
        }
        for (int i = 0; i < n; i++) {
            //将各个字母对应的个数添加至数组中
            temp1[s1.charAt(i) - 'a']++;
            temp2[s2.charAt(i) - 'a']++;
        }
        //判断两个数组中对应的字母数量是否相同
        if (Arrays.equals(temp1, temp2)) {
            return true;
        }
        for (int i = n; i < m; i++) {
            //滑动窗口右端，向右移动一位
            temp2[s2.charAt(i) - 'a']++;
            //滑动窗口左端，向右移动一位，需要减去原本位于窗口最左侧的字母
            temp2[s2.charAt(i - n) - 'a']--;
            //判断字母数量是否一致
            if (Arrays.equals(temp1,temp2)){
                return true;
            }
        }
        return false;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-in-string/submissions/