567. 字符串的排列
问题
给定两个字符串 和
，写一个函数来判断
是否包含
的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入:
输出:
解释:包含
的排列之一
.
示例2:
输入:
输出:
注意：
- 输入的字符串只包含小写字母
- 两个字符串的长度都在 [1, 10,000] 之间
解法
题目乍一看似乎没什么好办法，暴力遍历总是行得通。但是时间复杂度嘛，嘿嘿。
接下来深挖一下题目，既然是判断是否包含
，那么我们总是可以排除一些明显不满足条件的地方：
-
-
接下来，我们假设中有
的排列
，那么这个排列
的长度肯定是
的长度
，实际上就是判断这两个字符串不管字母顺序是否相同，
判断两个字符串是否相同可以用一个长度为26的数组，遍历第一个，将字母出现的次数记下来，然后遍历另一个字符串将数组中字母出现的次数减小一，当次数减小到-1时，代表不相同，直接返回false。当遍历完仍然没有返回时，那么两个字符串肯定是相同的。
我们可以设置两个指针，一个起始指针，一个结束指针
，并且有
。此时，从
指针处往回判断。至于为什么从
处往回走而不是从
处往前走是因为，我们注意到这样一种情况，当
处的字符在数组中出现次数已经减到0时，
处的字符必然不在排列
中，此时，
可以直接跳到
处，可以直接过滤掉部分字符。这样也就不用遍历必然失败的场景了。
代码
java实现
class Solution {
public boolean checkInclusion(String s1, String s2) {
// 特殊情况直接跳出
if (s1 == null || s2 == null || s2.length() < s1.length()) {
return false;
}
// 初始化一个数组，将s1的字母出现次数保存在这个数组中去。
int[] map = new int[26];
int length = s1.length();
//遍历s1放入map
for (int i = 0; i < length; i++) {
map[s1.charAt(i) - 'a']++;
}
//遍历s2，此时注意到这样一个情况，如果s2包含s1，那么s2子串的长度必然等于s1，因此，可以设置两个指针。
int start = 0, end = length - 1;
while (end < s2.length()) {
// 这里是一个注意点，需要注意不能直接用map处理，否则会导致第一次false后，后面的判断全是false
int[] temp = map.clone();
while (end >= start) {
if (temp[s2.charAt(end) - 'a']-- == 0) {
break;
}
end--;
}
//上一层有两种跳出方式，一种break；一种是正确判断完了。需要区分一下。
if (end < start) {
//这种是正常判断完成了。直接返回true
return true;
} else {
//此时注意到这样一种情况，end处必然不能在s2子串中出现。那么start = end+1,end = start+length-1 可以跳过start与end之间的字符，因为这部分字符必然不满足条件。
start = end + 1;
end = start + length - 1;
}
}
return false;
}
}
