567. Permutation in String (Sliding window)

567. Permutation in String

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

1. The input strings only contain lower case letters.

2. The length of both given strings is in range [1, 10,000].

My Solutions:

用 sliding window的思想，用array储存char出现的评率，比较每个s1.length() 长度的window，s1 和s2是否一样

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        
        int[] arr1 = new int[26], arr2 = new int[26];
        
        // 建字典，储存s1长度的字符出现频率
        for (int i = 0; i < s1.length(); i++) {
            arr1[s1.charAt(i) - 'a']++;
            arr2[s2.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < s2.length() - s1.length(); i++) {
            if (match(arr1, arr2)) return true;
            arr2[s2.charAt(i) - 'a']--; // arr2里当前字母的频率减1 --> sliding window的左边少一格
            arr2[s2.charAt(i + s1.length()) - 'a']++; // sliding window的右边多一格
        }
        
        return match(arr1, arr2);
    }
    
    // 检查两个数组是否存有相同字母
    public boolean match(int[] arr1, int[] arr2) {
        for (int i = 0; i < 26; i++) {
            if (arr1[i] != arr2[i]) return false;
        }
        return true;
    }
}