May LeetCoding Challenge18 之 滑动窗口2.0

滑动窗口适用于两个字符串，判断一区间内字符出现的次数 是否 相匹配。其实现方式可以为map 或者 array。

S1 和 S2为两个字符串，S1长度len1小于S2长度len2

步骤如下：

1.申请两个map或者array，首先统计S1 的字符 及出现的次数，形成count1

2.用left = 0，right =  len1。将0到len1-1的区间的字符存入count2。这样写的目的时防止out of index range。

3.当right < len2时，先将right所指字符存入count2中，再与count1比较，如果相等返回true。然后在count1中删除left所指字符，将left++，right++。实现窗口向后移动。

JAVA

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if(s1.length() > s2.length()) return false;
        Map<Character, Integer> count1 = new HashMap<>();
        Map<Character, Integer> count2 = new HashMap<>();
        for(char c: s1.toCharArray()){
            count1.put(c, count1.getOrDefault(c, 0)+1);
        }
        int left = 0;
        int right = s1.length()-1;
        for(char c: s2.substring(left, right).toCharArray()){
            count2.put(c, count2.getOrDefault(c, 0)+1);
        }
        while(right < s2.length()){
            char c = s2.charAt(right);
            count2.put(c, count2.getOrDefault(c, 0)+1);
            if(count1.equals(count2)) return true;
            char t = s2.charAt(left);
            if(count2.get(t) == 1){
                count2.remove(t); //remove 删除map的key
            }
            else{
                count2.put(t, count2.get(t)-1);
            }
            left++;
            right++;
        }
        return false;
    }
}

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if(s1.length() > s2.length()) return false;
        int[] count1 = new int[26];
        int[] count2 = new int[26];
        for(char c: s1.toCharArray()){
            count1[(int)(c - 'a')]++;
        }
        int left = 0;
        int right = s1.length()-1;
        for(char c: s2.substring(left, right).toCharArray()){
            count2[(int)(c - 'a')]++;
        }
        while(right < s2.length()){
            char c = s2.charAt(right);
            count2[(int)(c - 'a')]++;
            if(matches(count1, count2)) return true;
            char t = s2.charAt(left);
            count2[(int)(t - 'a')]--;
            left++;
            right++;
        }
        return false;
    }
    public boolean matches(int[] count1, int[] count2){
        for(int i = 0; i < 26; i++){
            if(count1[i] != count2[i]) return false;
        }
            return true;
    }
}

Python3

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s2) < len(s1): return False
        count1 = collections.Counter(s1)
        left, right = 0, len(s1) - 1
        count2 = collections.Counter(s2[left : right])
        while right < len(s2):
            count2[s2[right]] += 1
            if count1 == count2:
                return True
            count2[s2[left]] -= 1
            if count2[s2[left]] == 0:
                del count2[s2[left]]
            left += 1
            right += 1
        return False

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s2) < len(s1): return False
        count1 = [0]*26
        count2 = [0]*26
        for c in s1:
            count1[ord(c) - ord('a')] += 1
        left, right = 0, len(s1) - 1
        for c in s2[left : right]:
            count2[ord(c) - ord('a')] += 1
        while right < len(s2):
            count2[ord(s2[right]) - ord('a')] += 1
            if count1 == count2:
                return True
            count2[ord(s2[left]) - ord('a')] -= 1
            left += 1
            right += 1
        return False