567.字符串的排列

我们先来分别统计s1和s2中前n1个字符串中各个字符出现的次数,其中n1为字符串s1的长度,这样如果二者字符出现次数的情况完全相同,说明s1和s2中前n1的字符互为全排列关系,那么符合题意了,直接返回true。如果不是的话,那么我们遍历s2之后的字符,对于遍历到的字符,对应的次数加1,由于窗口的大小限定为了n1,所以每在窗口右侧加一个新字符的同时就要在窗口左侧去掉一个字符,每次都比较一下两个哈希表的情况,如果相等,说明存在。

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int len1=s1.length(),len2=s2.length();
        if(len1>len2) return false;
        int[] count1=new int[128];
        int[] count2=new int[128];
        for(int i=0;i<len1;i++){
            ++count1[s1.charAt(i) - 'a'];
            ++count2[s2.charAt(i) - 'a'];
        }
        if(Arrays.equals(count1,count2)){
            return true;            
        }
        for(int i=len1;i<len2;i++){
            ++count2[s2.charAt(i)-'a'];
            --count2[s2.charAt(i-len1)-'a'];
            if(Arrays.equals(count1,count2)){
                return true;
            }
        }
        return false;
    }
}
上一篇:实验4 继承


下一篇:NHANSE数据库的介绍及使用(二)