题目:
字符串的排列
解法:
只要在一个s1长度的固定大小的窗口内, 如果有其中的字符数量相等, 即认为第一个字符串s1的排列之一是第二个字符串s2的子串
public boolean checkInclusion(String s1, String s2) {
if (s1 == null || s2 == null) {
return false;
}
if (s1 == "") {
return true;
}
if (s1.length() > s2.length()) {
return false;
}
int[] s1CharCount = new int[26];
int[] slidingWindow = new int[26];
for (int i = 0; i < s1.length(); i++) {
// 对应字符相加
s1CharCount[s1.charAt(i) - 'a']++;
}
int s1Len = s1.length();
// 窗口左边界, 包含
int lo = 0;
// 窗口右边界, 包含
int hi = s1Len - 1;
// 初始化窗口的字符个数, 暂时不包含hi
for (int i = lo; i < hi; i++) {
slidingWindow[s2.charAt(i) - 'a']++;
}
while (hi < s2.length()) {
slidingWindow[s2.charAt(hi) - 'a']++;
// 对比两个数组是否相等
if (Arrays.equals(s1CharCount, slidingWindow)) {
return true;
} else {
slidingWindow[s2.charAt(lo++) - 'a']--;
}
hi++;
}
return false;
}
