Poison

438. Find All Anagrams in a String

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
40
41
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> startIndexList = new ArrayList<>();
if (p.length() > s.length()) {
return startIndexList;
}

int[] targetCountMap = new int[26];
int targetDistinctCharCount = 0;
for (int i = 0; i < p.length(); i++) {
if (targetCountMap[p.charAt(i) - 'a']++ == 0) {
targetDistinctCharCount++;
}
}

int[] windowCountMap = new int[26];
int distinctCharCount = 0;
int i = 0;
for (int j = 0; j < s.length(); j++) {
int offset = s.charAt(j) - 'a';
if (++windowCountMap[offset] == targetCountMap[offset]) {
distinctCharCount++;
}

while (distinctCharCount == targetDistinctCharCount) {
// 当不同的字符数已经匹配时,说明窗口字符串长度大于等于目标字符串长度,此时检查字符串长度是否相同
if (j - i + 1 == p.length()) {
startIndexList.add(i);
}

// 尝试缩小窗口
int leftmostOffset = s.charAt(i++) - 'a';
if (windowCountMap[leftmostOffset]-- == targetCountMap[leftmostOffset]) {
distinctCharCount--;
}
}
}

return startIndexList;
}
}
Reference

438. Find All Anagrams in a String
剑指 Offer II 015. 字符串中的所有变位词