Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
代码
Approach #1 Sliding Window with HashMap
Complexity Analysis
Time complexity: O(Ns+Np) since it's one pass along both strings.
Space complexity: O(1), because pCount and sCount contain not more than 26 elements.
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int ns = s.length(), np = p.length();
if (ns < np) return new ArrayList();
Map<Character, Integer> pCount = new HashMap();
Map<Character, Integer> sCount = new HashMap();
// build reference hashmap using string p
for (char ch : p.toCharArray()) {
if (pCount.containsKey(ch)) {
pCount.put(ch, pCount.get(ch) + 1);
}
else {
pCount.put(ch, 1);
}
}
List<Integer> output = new ArrayList();
// sliding window on the string s
for (int i = 0; i < ns; ++i) {
// add one more letter
// on the right side of the window
char ch = s.charAt(i);
if (sCount.containsKey(ch)) {
sCount.put(ch, sCount.get(ch) + 1);
}
else {
sCount.put(ch, 1);
}
// remove one letter
// from the left side of the window
if (i >= np) {
ch = s.charAt(i - np);
if (sCount.get(ch) == 1) {
sCount.remove(ch);
}
else {
sCount.put(ch, sCount.get(ch) - 1);
}
}
// compare hashmap in the sliding window
// with the reference hashmap
if (pCount.equals(sCount)) {
output.add(i - np + 1);
}
}
return output;
}
}
Approach #2 Sliding Windwo with Array
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int ns = s.length(), np = p.length();
if (ns < np) return new ArrayList();
int[] pCount = new int[26];
int[] sCount = new int[26];
for (char ch: p.toCharArray()) {
int index = ch - 'a';
pCount[index]++;
}
List<Integer> output = new ArrayList();
for (int i = 0; i < ns; i++) {
int index = s.charAt(i) - 'a';
aCount[index]++;
if (i >= np) {
index = s.charAt(i - np) - 'a';
aCount[index]++;
}
if (Arrays.equals(pCount, sCount)) {
output.add(i - np + 1);
}
}
return output;
}
}