567. Permutation in String

问题
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

将要查找的组合加入数组,数值为字符出现的次数。
滑动窗口,入窗口对应的元素数值-1,出窗口对应的元素数值+1。
每次移动窗口都检验一次数组的数值是否全部为0,如果是真,则返回真。
小技巧:直接用数组来记录字符出现的次数,用字符减去与’a’的差作为下标。

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
35
36
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()){
return false;
}

int[] dic = new int[26];
for (int i = 0; i < s1.length(); i++){
dic[s1.charAt(i)-'a']++;
dic[s2.charAt(i)-'a']--;
}

int i = 0;
int j = s1.length();

while( j < s2.length() ){
if ( allZero(dic) ){
return true;
}
dic[s2.charAt(i)-'a']++;
dic[s2.charAt(j)-'a']--;
i++;
j++;
}
return allZero(dic);
}

private boolean allZero(int[] dic){
for (int num : dic){
if ( num != 0 ){
return false;
}
}
return true;
}
}
Author

Xander

Posted on

2022-04-07

Updated on

2022-04-20

Licensed under

Comments