LeetCode刷题【剑指 Offer II 014】字符串中的变位词

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

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

示例 1：

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

示例 2：

输入: s1= "ab" s2 = "eidboaoo"
输出: False

提示：

• 1 <= s1.length, s2.length <= 104
• s1 和 s2 仅包含小写字母

注意：本题与主站 567 题相同： https://leetcode-cn.com/problems/permutation-in-string/

滑动窗口基本思路

基本滑动窗口算法
挪一格，修改一下统计数量，然后对比两个数组内是否相同

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length()>s2.length()){
            return false;
        }
        
        int[] count = new int[26];
        int[] window = new int[26];
        int idx = -1;
        while (++idx < s1.length()){
            count[s1.charAt(idx)-'a']++;
            window[s2.charAt(idx)-'a']++;
        }
        if (Arrays.equals(count,window)){
            return true;
        }
        idx--;
        while (++idx < s2.length()){
            System.out.println( idx );
            window[s2.charAt( idx - s1.length() ) - 'a']--;
            window[s2.charAt( idx ) - 'a']++;
            if (Arrays.equals(count,window)){
                return true;
            }
        }
        return false;
    }

}

滑动窗口diffArr判断算法，判断26个字母数量是否为0，如果是都是0则代表能匹配

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length()>s2.length()){
            return false;
        }

        int[] diffArr = new int[26];
        int idx = -1;
        int diffCount = 0;
        while (++idx < s1.length()){
            diffArr[s1.charAt(idx)-'a']++;
            diffArr[s2.charAt(idx)-'a']--;
        }
        boolean flag = true;
        for (int i = 0; i < 26; i++) {
            if (diffArr[i]!=0){
                flag =false;
                break;
            }
        }
        if (flag){
            return true;
        }
        --idx;
        while (++idx < s2.length()){
            diffArr[s2.charAt(idx-s1.length())-'a']++;
            diffArr[s2.charAt(idx)-'a']--;
            flag = true;
            for (int i = 0; i < 26; i++) {
                if (diffArr[i]!=0){
                    flag =false;
                    break;
                }
            }
            if (flag){
                return true;
            }
        }
        return false;
    }

}

第二种滑动窗口的理解稍微绕个弯，每当diffArr中有一个不是0的，说明有一个差异点，
然后接下来窗口滑动过程中 需要在修改前判断

1. 这个值是不是0，如果是0，修改了之后diffCount需要加1，
2. 如果不是0.修改之后会不会变0.如果会变0，diffCount减1
3. 如果修改后不会变0，则diffCount不需要变更

if判断太多，效率甚至不如上一个遍历一下长度只有26的diffArr数组

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length()>s2.length()){
            return false;
        }

        int[] diffArr = new int[26];
        int idx = -1;
        int diffCount = 0;
        while (++idx < s1.length()){
            diffArr[s1.charAt(idx)-'a']++;
            diffArr[s2.charAt(idx)-'a']--;
        }
        int i = -1;
        while (++i<26){
            diffCount += diffArr[i]==0?0:1;
        }
        if (diffCount==0){
            return true;
        }

        --idx;
        while (++idx < s2.length()){
            int before = s2.charAt(idx-s1.length())-'a';
            int current = s2.charAt(idx)-'a';
            if (before == current){
                continue;
            }
            if (diffArr[before]==-1){
                diffCount--;
            }
            if (diffArr[before] == 0){
                diffCount++;
            }
            diffArr[before]++;

            if (diffArr[current]==1){
                diffCount--;
            }
            if (diffArr[current]==0){
                diffCount++;
            }
            diffArr[current]--;
            if (diffCount == 0){
                return true;
            }
        }
        return false;
    }

}