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.
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".
思路：
sliding window滑动窗口
1. traverse String T, using a map to record each char's frequency
2. use [leftMost to i] to maintain a sliding window, making sure that each char's frequency in such sliding window == that in T
3. if mapS [S.charAt(leftMost)] > mapT [S.charAt(leftMost)] , it signs we can move sliding window
4. how to find the next sliding window? move leftMost, meanwhile, decrement mapS [S.charAt(leftMost)] until we find each frequency in [leftMost to i] == that in T
代码：
1 class Solution { 2 public List<Integer> findAnagrams(String S, String T) { 3 List<Integer> resultList = new ArrayList<>(); 4 if (S == null || S.length() == 0) return resultList; 5 6 int[] mapT = new int[256]; 7 int[] mapS = new int[256]; 8 9 int count = 0; 10 int leftMost = 0; 11 for(int i = 0; i < T.length(); i++){ 12 mapT[T.charAt(i)] ++; 13 } 14 15 for(int i = 0; i < S.length(); i++) { 16 char s = S.charAt(i); 17 mapS[s]++; 18 if (mapT[s] >= mapS[s]) { 19 count++; 20 } 21 22 if (count == T.length()) { 23 while (mapS[S.charAt(leftMost)] > mapT[S.charAt(leftMost)]) { 24 if (mapS[S.charAt(leftMost)] > mapT[S.charAt(leftMost)]) { 25 mapS[S.charAt(leftMost)]--; 26 } 27 leftMost++; 28 } 29 if (i - leftMost + 1 == T.length()) { 30 resultList.add(leftMost); 31 } 32 } 33 } 34 return resultList; 35 } 36 }
转载于:https://www.cnblogs.com/liuliu5151/p/9810073.html
