Sword finger offer II 014 Anagrams in strings

subject

link ：https://leetcode.cn/problems/MPnaiL/

Given two strings s1 and s2, Write a function to judge s2 Does it include s1 An anamorphic word of .

let me put it another way , One of the permutations of the first string is the... Of the second string Substring .

Ideas

The description of the topic is not clear , What I understand is ： All the characters in the first string are arranged arbitrarily , Can form a substring in the second string .

Then the condition we have to meet is ：

1. s2 The length of the qualified substring in is equal to s1 The length of
2. s2 The number of occurrences of each lowercase letter in this substring , be equal to s1 The number of occurrences of each lowercase letter in

Continuous substring , It's easy to think of double pointers . And count the number of lowercase letters , Again, we are familiar with , Length can be used 26 Bit array （ Hashtable ）, Save the number of occurrences of each letter .

solution ： Double pointer + Hashtable

Logic

1. Use a length 26 An array of bits holds the number of occurrences of each lowercase letter
2. Traverse s1, Fill the array
3. Double pointer processing s2, First from 0 Start , Move the right pointer to the right s1.length-1 The location of . Every time I move , Look at the current subscript letter , And subtract... From the corresponding position in the array 1.
4. Both hands move to the right at the same time . Letter moved out by left pointer , Add... To the corresponding position of the array 1, The letter in which the right pointer moves , Subtract... From the corresponding position of the array 1. Each move counts whether the array is 0, Yes, go back to true.

Code

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

    int[] counts = new int[26];
    for (int i = 0; i < s1.length(); i++) {
        counts[s1.charAt(i) - 'a'] += 1;
        counts[s2.charAt(i) - 'a'] -= 1;
    }
    if (allZero(counts)) {
        return true;
    }

    for (int i = s1.length(); i < s2.length(); i++) {
        counts[s2.charAt(i) - 'a'] -= 1;
        counts[s2.charAt(i-s1.length()) - 'a'] += 1;
        if (allZero(counts)) {
            return true;
        }
    }

    return false;
}

public boolean allZero(int[] counts){
    for (int count : counts) {
        if (count != 0) {
            return false;
        }
    }
    return true;
}