字符串的排列

QUESTION:

给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。

换句话说,第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = “ab” s2 = “eidbaooo” 输出: True 解释: s2 包含 s1 的排列之一 (“ba”).

示例2:

输入: s1= “ab” s2 = “eidboaoo” 输出: False

注意:

输入的字符串只包含小写字母 两个字符串的长度都在 [1, 10,000] 之间

EXPLANATION:

题目的意思简单说就是:s1的字符打乱顺序后是否在s2中。
思路如下:
1.用一个26的数组来计算s1中每个字符的数量
2.对s2进行遍历,如果符合s1中的某个,那么就开始计数,记为start
3.接着往下遍历记为end
4.如果end指向的s2也在s1中,那么数量就减一
5.如果数量减到0了,那么就说明已经完成
6.如果end指向的s2不在s1中,那么就将计数和数组复位
7.重新移动start,直到最后

SOLUTION:

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] tmp = checkInclusionArray(s1);
        int size = s1.length();
        int index = 0;
        while (index<s2.length()){
            int point = index;
            if(tmp[s2.charAt(index)-'a'] != 0){
                while (size!=0 && point<s2.length()){
                    int count = tmp[s2.charAt(point)-'a'];
                    if(count==0) break;
                    else {
                        tmp[s2.charAt(point)-'a']--;
                        size--;
                        point++;
                    }
                }
                if(size == 0) return true;
                tmp = checkInclusionArray(s1);
                size = s1.length();
            }
            index++;
        }
        return false;
    }
    public static int[] checkInclusionArray(String s1){
        int[] template = new int[26];
        for(char c : s1.toCharArray()) template[c-'a']++;
        return template;
    }
}