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

method 1. s2挨个拿与s1相同长度的substring与s1比较是不是permutation
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        if (len1 > len2) return false;

        for(int i = 0; i < (len2 - len1) + 1; i++) {
            String sub = s2.substring(i, i + len1);
            if(isPermutation(s1, sub)) return true;
        }
        return false;
    }

    private boolean isPermutation(String A, String B) {
        int[] count = new int[26];
        for(int i = 0; i < A.length(); i++) {
            count[A.charAt(i) - 'a']++;
            count[B.charAt(i) - 'a']--; 
        }

        for(int i = 0; i < 26; i++) {
            if(count[i] != 0) return false;
        }

        return true;
    }
}


method 2. 先扫一遍字符串s1，统计各个字母的个数，取s2前s1长度个字符，匹配个数是否相符，
若不相符，去除最前面的字符，加入后一个字符，重新比对，直至个数匹配，或扫描完s2。
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        if (len1 > len2) return false;

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

        for(int i = 0; i < len2 - len1; i++) {
            count[s2.charAt(i) - 'a']++; //去除前一个字母的影响
            count[s2.charAt(i + len1) - 'a']--; //加入后一个字母的影响
            if(allZero(count)) return true;
        }
        return false;
    }

    private boolean allZero(int[] count) {
        for(int i = 0; i < 26; i++) {
            if(count[i] != 0) return false;
        }
        return true;
    }
}