567. Permutation in String - Medium

前往題目

想法

• 用hashmap，以及sliding window

思路

1. 用array存字母個數
2. 疊代整個s2，如果window>=s1的大小的時候，就可以比較s1和s2
3. 沒有的話把window的首字母數量-1，這樣才能保證window的大小和s1一致

Code

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // Build s1 array
        int[] s1Arr = new int[26];

        Arrays.fill(s1Arr, 0);

        for (char c : s1.toCharArray()) {
            s1Arr[c - 'a'] += 1;
        }

        int s1Size = s1.length();
        int[] s2Arr = new int[26];
        Arrays.fill(s2Arr, 0);

        // Go through s2
        for (int i = 0; i < s2.length(); ++i) {
            s2Arr[s2.charAt(i) - 'a'] += 1;
            // Window is the same size as s1
            if (i >= s1Size - 1) {
                // Same content
                if (Arrays.equals(s1Arr, s2Arr)) return true;
                // Remove the head char for new window
                s2Arr[s2.charAt(i - s1Size + 1) - 'a'] -= 1;
            }
        }
        return false;

    }
}