05 August 2008
判断一个字符串s2中是否存在一个子字符串，跟另一个字符串s1是否为permutation，也就是anagram，返回true或false
Ituiatively的滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1 == null || s1.length() == 0) {
return true;
}
if (s2.length() < s1.length()) {
return false;
}
int left = 0;
int right = s1.length(); //左开右闭
while (right <= s2.length()) {
if (checkAnagram(s1, s2.substring(left, right))) {
return true;
}
left++;
right++;
}
return false;
}
private boolean checkAnagram(String str1, String str2) {
int[] arr = new int[256];
int len = str1.length();
for (int i = 0; i < len; i++) {
arr[str1.charAt(i)]++;
arr[str2.charAt(i)]--;
}
for (int i = 0; i < 256; i++) {
if (arr[i] != 0) {
return false;
}
}
return true;
}
}