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:
The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

解析重点

1.s2的字串是s1的排列。那么，我们可以把查找过程分为两步。第一步，滑动窗口在s2上，步长为s1。第二步，比较滑动窗口字串和s1内容，判断是否是s1的排列。
2.第一步滑动s2好处理。第二步，我们要怎么处理呢，我们只需要统计两个串字母的数量是否相等即可。

java代码

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if(s1==null||s2==null||s1.length()>s2.length()) return false;
        int len1=s1.length(),len2=s2.length();
        int[] count=new int[26];
        for(int i=0;i<len1;i++){//初始化比较len1长度的串
            count[s1.charAt(i)-'a']--;
            count[s2.charAt(i)-'a']++;
        }
        if(allZero(count)) return true;
        for(int j=len1;j<len2;j++){//s2一直保持截取len1长度的串
            count[s2.charAt(j)-'a']++;//s2截取的串添加一个字符j
            count[s2.charAt(j-len1)-'a']--;//s2减少一个起始位置的字符（j-len1），这样保持s2截取的串一直是len1
            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;
    }    
}