字符串的排列

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

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

示例1:

1
2
3
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例2:

1
2
输入: s1= "ab" s2 = "eidboaoo"
输出: False

注意：

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

第一次代码（超时）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if(s1==null||s2==null)return false;
        if(s1.length()==0||s2.length()==0)return  false;
        char[] map=new char[s1.length()];
        for(int i=0;i<map.length;i++)
        {
            map[i]=0;
        }
        //在这里声明变量应该会快一些
        int num=-1;
        for(int i=0;i<s2.length();i++)
        {
            int begin=0;
            while(true)
            {
                num=s1.indexOf(s2.charAt(i),begin);
                if(num==-1)
                {
                    int flag=1;
                    for(int j=0;j<map.length;j++)
                    {
                        if(map[j]==0)
                        {
                            flag=0;
                        }
                        map[j]=0;
                    }
                    if(flag==1)return true;
                    break;
                }
                if(map[num]==0)
                {
                    map[num]=1;
                    break;
                } else {
                    //这里的意思是找到了，但是已经标记过了
                    begin=num;
                }
            }
        }
        return false;
    }
}

第二次代码（参考）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if(s1==null||s2==null)return false;
        if(s1.length()==0||s2.length()==0)return  false;
        char[] map=new char[26];

        int len=s1.length();
        for (int i=0;i<len;i++)
        {
            map[s1.charAt(i)-'a']++;
        }
        int i=0,j=0;
        for(;j<s2.length();)
        {
            map[s2.charAt(j)-'a']--;
            if(j-i+1==len)
            {
                int k=0;
                for(;k<26;k++)
                {
                    if(map[k]!=0)break;
                }
                if(k==26)return true;

                map[s2.charAt(i)-'a']++;
                i++;
            }
            j++;
        }
        return false;
    }
}