leet code 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

提示：

• 
• s1 和 s2 仅包含小写字母

题目解析

提取关键信息

• s1,s2都是仅仅是由小写字母组成
• 是否包含排列--而不是含有对应字符，即 s1 的排列是否是 s2 的子串之一
• 很显然适合用滑动窗口来解决

show code

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        if(len1 > len2) {
            return false;
        }
        // 创建一个数组，来保存  窗口内  各个字符出现的次数
        int[] count = new int[26];
        for(int i = 0;i < len1;i++) {
            count[s2.charAt(i) - 'a']++;
            count[s1.charAt(i) - 'a']--;
        }

        // 统计窗口内不同字符的个数
        int differ = 0;
        for(int i = 0;i < 26;i++) {
            if(count[i] != 0) {
                differ++;
            }
        }

        if(differ == 0) {
            return true;
        }

        // 遍历字符串 s2
        for(int i = 0;i < len2 - len1;i++) {
            // s2.charAt(i) 要移出窗口
            if(count[s2.charAt(i) - 'a'] == 1) {
                // 如果 count[s2.charAt(i) - 'a'] == 1 
                // 表示 这个字符  在窗口内 比 在s1中多出现了1次
                // 移出，相同字符个数 减少 1
                differ--;
            } else if(count[s2.charAt(i) - 'a'] == 0) {
                // 同理 这里增加 1
                differ++;
            }

            count[s2.charAt(i) - 'a']--;

            if(count[s2.charAt(i + len1) - 'a'] == -1) {
                differ--;
            } else if(count[s2.charAt(i + len1) - 'a'] == 0) {
                differ++;
            }

            count[s2.charAt(i + len1) - 'a']++;
            if(differ == 0) {
                return true;
            }
        }

        return false;
    }
}