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
| class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> startIndexList = new ArrayList<>();
if (s.length() < p.length()) {
return startIndexList;
}
int[] targetCountMap = new int[26];
for (int i = 0; i < p.length(); i++) {
targetCountMap[p.charAt(i) - 'a']++;
}
int[] windowCountMap = new int[26];
for (int j = 0; j < s.length(); j++) {
windowCountMap[s.charAt(j) - 'a']++;
if (j >= p.length() - 1) {
int i = j - p.length() + 1;
if (Arrays.equals(windowCountMap, targetCountMap)) {
startIndexList.add(i);
}
windowCountMap[s.charAt(i) - 'a']--;
}
}
return startIndexList;
}
}
|
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
37
38
39
| class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> startIndexList = new ArrayList<>();
if (s.length() < p.length()) {
return startIndexList;
}
int[] targetCountMap = new int[26];
int targetDistinctChars = 0;
for (int i = 0; i < p.length(); i++) {
if (targetCountMap[p.charAt(i) - 'a']++ == 0) {
targetDistinctChars++;
}
}
int[] windowCountMap = new int[26];
int matchedChars = 0;
int i = 0;
for (int j = 0; j < s.length(); j++) {
if (++windowCountMap[s.charAt(j) - 'a'] == targetCountMap[s.charAt(j) - 'a']) {
matchedChars++;
}
while (j - i + 1 > p.length()) {
if (windowCountMap[s.charAt(i) - 'a']-- == targetCountMap[s.charAt(i) - 'a']) {
matchedChars--;
}
i++;
}
if (matchedChars == targetDistinctChars && j - i + 1 == p.length()) {
startIndexList.add(i);
}
}
return startIndexList;
}
}
|
References
438. Find All Anagrams in a String
剑指 Offer II 015. 字符串中的所有变位词