2022-08-09 滑动窗口

剑指 Offer II 014. 字符串中的变位词

滑动窗口：在第二个字符串中每次滑行进行判断，
class Solution {
public boolean checkInclusion(String s1, String s2) {
// 判断第一个字符是否在里面

    // 在的话，截取从这个字符开始的长度
    //  计算起始到这个长度的哈希值

    int m=s1.length();
    int n=s2.length();
     int[] arr=new int[26];
      for(int i=0;i<m;i++){
       arr[s1.charAt(i)-'a']++;
    }
  
    boolean res=false;
    int index=0;
  
    for(int i=0;i<n-m+1;i++){
        if( arr[s2.charAt(i)-'a']!=0){
            index=i;
            // System.out.println(index);
          res=compare(s1,s2,index);
          if(res==true){
              break;
          }
        }
    }
    return res;

}
 public boolean compare(String s1,String s2,int index){
     int m=s1.length();
     int[] arr=new int[26];
      for(int i=0;i<m;i++){
       arr[s1.charAt(i)-'a']++;
       arr[s2.charAt(i+index)-'a']--;
    }
    for(int i=0;i<26;i++){
        if(arr[i]!=0){
            return false;
        }
    }
    return true;

 }

}