567. Permutation in String.md

LeetCode 567. Permutation in String

这道题是去找字符串s2中是否有s1的排列（其实和438 找所有的异位词类似，甚至情况更简单一些），用滑动窗口很简单就OK。这里最大的收获在于使用hashmap和数组的做法能相差8倍！！！！

Hashmap版本用时32ms， 超过29%

数组版本用时4ms,超过了98%

滑动窗口 使用hashmap计数

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int left = 0, right = 0;
        int match = 0;
    
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> needs = new HashMap<>();

        for (char c : s1.toCharArray()) needs.put(c, needs.getOrDefault(c, 0)+1);
        int length = s2.length();
        int length1 = s1.length();
        int size = needs.size();

        while (right < length) {
            char c = s2.charAt(right);
            if (needs.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0)+1);
                if (needs.get(c).equals(window.get(c)))
                    match++;
            }
            right++;

            while (match == size) {
                if (right - left == length1)
                    return true;
                char c2 = s2.charAt(left);
                if (needs.containsKey(c2)) {
                    if (needs.get(c2).equals(window.get(c2)))
                        match--;
                    window.put(c2, window.get(c2)-1);
                }
                left++;
            }
        }
        return false;
    }
}

滑动窗口 使用数组计数

这里因为只有小写字母，因此类似于计数排序的思想，使用数组来计数

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int left = 0, right = 0;
        int match = 0;
    
        int[] window = new int[26];
        int[] needs = new int[26];

        Arrays.fill(window, 0);
        Arrays.fill(needs, 0);

        for (char c : s1.toCharArray()) needs[c-'a']++;
        int len2 = s2.length();
        int len1 = s1.length();
        int size = 0;
        for (int i = 0; i < needs.length; i++)
            if (needs[i] != 0)
                size++;

        while (right < len2) {
            int idx = s2.charAt(right) - 'a';
            if (needs[idx] != 0) {
                window[idx]++;
                if (needs[idx] == window[idx])
                    match++;
            }
            right++;

            while (match == size) {
                if (right - left == len1)
                    return true;
                int idx2 = s2.charAt(left) - 'a';
                if (needs[idx2] != 0) {
                    if (needs[idx2] == window[idx2])
                        match--;
                    window[idx2]--;
                }
                left++;
            }
        }
        return false;
    }
}