Java
import java.util.ArrayList;
import java.util.List;
/**
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".
*/
public class Find_All_Anagrams_in_a_String {
public class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (p == null || s == null || s.length() < p.length()) return res;
int m = s.length(), n = p.length();
for (int i = 0; i < m-n+1; i++) {
String cur = s.substring(i, i+n);
if (helper(cur, p)) {
res.add(i);
}
}
return res;
}
public boolean helper(String a, String b) {
if (a == null || b == null || a.length() != b.length()) {
return false;
}
int[] dict = new int[26];
// 2*logN is better than sorting 2*NlogN
for (int i = 0; i < a.length(); i++) {
char ch = a.charAt(i);
dict[ch-'a']++;
}
for (int i = 0; i < b.length(); i++) {
char ch = b.charAt(i);
dict[ch-'a']--;
if (dict[ch-'a'] < 0) return false;
}
return true;
}
}
}Java
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> indices = new ArrayList<Integer>();
if (s == null || p == null || s.length() < p.length())
return indices;
int sLength = s.length();
int pLength = p.length();
int[] sCount = new int[26];
int[] pCount = new int[26];
for (int i = 0; i < pLength; i++) {
sCount[s.charAt(i) - 'a']++;
pCount[p.charAt(i) - 'a']++;
}
if (match(sCount, pCount))
indices.add(0);
for (int i = pLength; i < sLength; i++) {
char prevC = s.charAt(i - pLength), curC = s.charAt(i);
sCount[prevC - 'a']--;
sCount[curC - 'a']++;
if (match(sCount, pCount))
indices.add(i - pLength + 1);
}
return indices;
}
public boolean match(int[] sCount, int[] pCount) {
for (int i = 0; i < 26; i++) {
if (sCount[i] != pCount[i])
return false;
}
return true;
}
}