438. Find All Anagrams in a String
Two pointers, sliding window + Hash table.
参考了这个帖子.
Similar to 76. Minimum Window Substring
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
Map<Character, Integer> map = new HashMap<>();
for (char c : p.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
int counter = map.size();
int start = 0;
int end = 0;
while (end < s.length()) {
char c = s.charAt(end);
if (map.containsKey(c)) {
map.put(c, map.get(c) - 1);
if (map.get(c) == 0) {
counter --;
}
}
end ++;
while (counter == 0) {
char temp = s.charAt(start);
if (map.containsKey(temp)) {
map.put(temp, map.get(temp) + 1);
if (map.get(temp) > 0) {
counter++;
}
}
if (end - start == p.length()) {
res.add(start);
}
start ++;
}
}
return res;
}
}
另一种写法:
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int[] map = new int[256];
for (char c : p.toCharArray()) {
map[c] ++;
}
int left = 0;
int right = 0;
int count = p.length();
while (right < s.length()) {
if (map[s.charAt(right)] >= 1) {
count --;
}
map[s.charAt(right)]--;
right ++;
if (count == 0) {
res.add(left);
}
if (right - left == p.length()) {
if (map[s.charAt(left)] >= 0) {
count ++;
}
map[s.charAt(left)] ++;
left++;
}
}
return res;
}
}