567.字符串的排列

一、题目

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

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

示例一：

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

示例二：

输入：s1= “ab” s2 = “eidboaoo”
输出：false

提示：

1 <= s1.length, s2.length <= 10^4
s1和s2仅包含小写字母

二、相关链接

题目链接：https://leetcode-cn.com/problems/permutation-in-string/
参考题解：https://leetcode-cn.com/problems/permutation-in-string/solution/zhu-shi-chao-xiang-xi-de-hua-dong-chuang-rc7d/

三、解题思路

解法：哈希表+移动窗口
思路：
- 1.移动窗口放在s2中，且长度等于s1
- 2.s1排列之一 = 长度相等 + 每个字符数量一致

四、代码

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        //用哈希表存s1中每个字符出现的次数
        //因为判断s2是否包含s1的某一个排列，所以只需要s2中某个连续子串的字符跟次数跟s1对应则为true
        Map<Character, Integer> s1Map = new HashMap<>();
        for(char c:s1.toCharArray()){
            //记录每个字符出现次数，get的时候不存在则默认为0
            s1Map.put(c,s1Map.getOrDefault(c,0)+1);
        }

        //s2的移动窗口(与s1长度一致)
        int left = 0;
        int right = s1.length()-1;

        while(right<s2.length()) {
            //如果有某个窗口为true，则说明s1的排列之一是s2的子串，return true
            if(this.isTheSameCharacterCount(s1Map,s2.substring(left,right+1))){
                return true;
            }

            //窗口向右滑动
            left++;
            right++;
        }

        return false;
    }

    /**
     * str中字符所包含的数量是否与targetMap一致
     * ps.    str长度=targetMap中value总和
     */
    public boolean isTheSameCharacterCount(Map<Character, Integer> targetMap, String str){
        Map<Character, Integer> resultMap = new HashMap<>();
        for(char c : str.toCharArray()) {
            
            //查询获取s1中c的数量
            int targetCount = targetMap.getOrDefault(c,0);
            if(targetCount == 0) {
                //targetMap不存在c字符，故结果不一致
                return false;
            }

            //查询s2中滑动窗口c的数量
            int count = resultMap.getOrDefault(c,0);
            if(count >= targetCount) {
                //str包含比targetMap多的字符，故结果不一致
                return false;
            }

            //记录str的c字符数量+1
            resultMap.put(c,count+1);
        }

        return true;
    }
}