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".
1.Brute Force
计算出p中所有char之和，然后从s中不断匹配和相同的串，然后对这些串的字符与p进行逐一比较。时间复杂度O(n*l)
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList();
int pSum = 0;
for (char c : p.toCharArray()) {
pSum += c;
}
int sSum = 0;
for (int i = 0; i < s.length(); i++) {
sSum += s.charAt(i);
if (i >= p.length() - 1) {
if (sSum == pSum) {
boolean match = true;
for (int j = i - p.length() + 1; j <= i; j++) {
if (p.indexOf(s.charAt(j)) < 0) {
match = false;
break;
}
}
if (match) result.add(i - p.length() + 1);
}
sSum -= s.charAt(i - p.length() + 1);
}
}
return result;
}
}
2.Two Pointers
利用一个数组保存p中所有字符出现的次数。用两个指针划分出一个长度为p的窗口，另外用一个变量记录窗口中匹配到的字符数量，通过窗口不断向后滑动，最终实现一次遍历得到结果，时间复杂度O(n)
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (p.length() > s.length()) return result;
int mark[] = new int[26];
for (char c : p.toCharArray()) mark[c - 'a']++;
int start = 0, end = 0, count = 0;
while (end < s.length()) {
if (--mark[s.charAt(end++) - 'a'] >= 0) count++;
if (count == p.length()) result.add(start);
if (end - start == p.length() && ++mark[s.charAt(start++) - 'a'] > 0) count--;
}
return result;
}
}