三刷 06/2022
Version #1 Sliding Window
Time O(N) - N is the length of the longer string
Space O(26) ~ O(1)
Runtime: 10 ms, faster than 82.16% of Java online submissions for Find All Anagrams in a String.
Memory Usage: 48.1 MB, less than 46.53% of Java online submissions for Find All Anagrams in a String.
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int[] count = new int[26];
for (int i = 0; i < p.length(); i++) {
count[p.charAt(i) - 'a']++;
}
List<Integer> result = new ArrayList<>();
int matchCount = 0;
int start = -1;
// (start, end]
for (int end = 0; end < s.length(); end++) {
int index = s.charAt(end) - 'a';
count[index]--;
if (count[index] >= 0) {
matchCount++;
}
while (count[index] < 0) {
start++;
int sIndex = s.charAt(start) - 'a';
count[sIndex]++;
if (count[sIndex] > 0) {
matchCount--;
}
}
if (matchCount == p.length()) {
result.add(start + 1);
}
}
return result;
}
}
//move right everytime, if the character exists in p's hash, decrease the count //current hash value >= 1 means the character is existing in p if (hash[s.charAt(right++)]-- >= 1) count--; //when the count is down to 0, means we found the right anagram //then add window's left to result list if (count == 0) list.add(left); //if we find the window's size equals to p, then we have to move left (narrow the window) to find the new match window //++ to reset the hash because we kicked out the left //only increase the count if the character is in p //the count >= 0 indicate it was original in the hash, cuz it won't go below 0 if (right - left == p.length() && hash[s.charAt(left++)]++ >= 0) count++; }”
一刷
注意counter数的是需要的char个数
如果char不在target里面，那么右指针-1左指针+1，两者只会互相抵消 永远不会大于0
只有当left扫过大于0的才是曾经存在于target里面的char，才能影响counter
95.80 %
public class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s == null || p == null || s.length() < p.length()) return result;
//only lowercase letters
int[] hash = new int[26];
int counter = 0; //keep track of #desired letters
int index;
//Generate the original count of each char
for (int i = 0; i < p.length(); i++) {
index = p.charAt(i) - 'a';
hash[index]++;
counter++;
}
int left = 0, right = 0;
while (right < s.length()) {
index = s.charAt(right++) - 'a';
if (--hash[index] >= 0) {
counter--;
}
while (counter == 0) {
if ((right - left) == p.length()) {
result.add(left);
}
index = s.charAt(left++) - 'a';
if (++hash[index] > 0) counter++;
}
}
return result;
}
}
二刷
88.62 %
class Solution {
public List<Integer> findAnagrams(String s, String p) {
if (s == null || p == null) return null;
List<Integer> result = new ArrayList<>();
int pLength = p.length();
int[] counter = new int[26];
int match = 0;
for (int i = 0; i < pLength; i++) {
counter[p.charAt(i) - 'a']++;
match++;
}
// [left, right] -> right - left + 1 == pLength -> remove left
//s . . . . . .
int left = 0, right = 0;
for (right = 0; right < s.length(); right++) {
if (--counter[s.charAt(right) - 'a'] >= 0) match--;
if (match == 0) result.add(left);
if (right - left + 1 == pLength) {
if (++counter[s.charAt(left) - 'a'] > 0) match++;
left++;
}
}
return result;
}
}
