给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
示例 1：
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例 2：
输入: s1= "ab" s2 = "eidboaoo" 输出: False
提示：
1 <= s1.length, s2.length <= 104s1和s2仅包含小写字母
注意：本题与主站 567 题相同： https://leetcode-cn.com/problems/permutation-in-string/
Related Topics
滑动窗口基本思路
基本滑动窗口算法
挪一格，修改一下统计数量，然后对比两个数组内是否相同
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length()>s2.length()){
return false;
}
int[] count = new int[26];
int[] window = new int[26];
int idx = -1;
while (++idx < s1.length()){
count[s1.charAt(idx)-'a']++;
window[s2.charAt(idx)-'a']++;
}
if (Arrays.equals(count,window)){
return true;
}
idx--;
while (++idx < s2.length()){
System.out.println( idx );
window[s2.charAt( idx - s1.length() ) - 'a']--;
window[s2.charAt( idx ) - 'a']++;
if (Arrays.equals(count,window)){
return true;
}
}
return false;
}
}滑动窗口diffArr判断算法，判断26个字母数量是否为0，如果是都是0则代表能匹配
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length()>s2.length()){
return false;
}
int[] diffArr = new int[26];
int idx = -1;
int diffCount = 0;
while (++idx < s1.length()){
diffArr[s1.charAt(idx)-'a']++;
diffArr[s2.charAt(idx)-'a']--;
}
boolean flag = true;
for (int i = 0; i < 26; i++) {
if (diffArr[i]!=0){
flag =false;
break;
}
}
if (flag){
return true;
}
--idx;
while (++idx < s2.length()){
diffArr[s2.charAt(idx-s1.length())-'a']++;
diffArr[s2.charAt(idx)-'a']--;
flag = true;
for (int i = 0; i < 26; i++) {
if (diffArr[i]!=0){
flag =false;
break;
}
}
if (flag){
return true;
}
}
return false;
}
}第二种滑动窗口的理解稍微绕个弯，每当diffArr中有一个不是0的，说明有一个差异点，
然后接下来窗口滑动过程中 需要在修改前判断
- 这个值是不是0，如果是0，修改了之后
diffCount需要加1， - 如果不是0.修改之后会不会变0.如果会变0，
diffCount减1 - 如果修改后不会变0，则
diffCount不需要变更
if判断太多，效率甚至不如上一个遍历一下长度只有26的diffArr数组
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length()>s2.length()){
return false;
}
int[] diffArr = new int[26];
int idx = -1;
int diffCount = 0;
while (++idx < s1.length()){
diffArr[s1.charAt(idx)-'a']++;
diffArr[s2.charAt(idx)-'a']--;
}
int i = -1;
while (++i<26){
diffCount += diffArr[i]==0?0:1;
}
if (diffCount==0){
return true;
}
--idx;
while (++idx < s2.length()){
int before = s2.charAt(idx-s1.length())-'a';
int current = s2.charAt(idx)-'a';
if (before == current){
continue;
}
if (diffArr[before]==-1){
diffCount--;
}
if (diffArr[before] == 0){
diffCount++;
}
diffArr[before]++;
if (diffArr[current]==1){
diffCount--;
}
if (diffArr[current]==0){
diffCount++;
}
diffArr[current]--;
if (diffCount == 0){
return true;
}
}
return false;
}
}
