438. Find All Anagrams in a String
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". 一开始我用了一种O(N^2)的方法，超时。如下： public class Solution { public List<Integer> findAnagrams(String s, String p) { if(p.length()>s.length() || s==null || p==null) return new ArrayList(); List<Character> list = new LinkedList<>(); List<Integer> res = new ArrayList<>(); int n=p.length(); for(int i=0; i<s.length()-n+1; i++){ boolean find = true; for(int k=0; k<n; k++){ list.add(p.charAt(k)); } for(int j=i; j<i+n; j++){ if(!list.contains(s.charAt(j))) {find=false;break;} else{ int index = list.indexOf(s.charAt(j)); list.remove(index); } } list.clear(); if(find) res.add(i); } return res; } }用滑动窗口算法的话，类似这种的substring search problem，都可以用O(N)的时间复杂度解决掉。
算法的模版如下：
public class Solution { public List<Integer> slidingWindowTemplateByHarryChaoyangHe(String s, String t) { //init a collection or int value to save the result according the question. List<Integer> result = new LinkedList<>(); if(t.length()> s.length()) return result; //create a hashmap to save the Characters of the target substring. //(K, V) = (Character, Frequence of the Characters) Map<Character, Integer> map = new HashMap<>(); for(char c : t.toCharArray()){ map.put(c, map.getOrDefault(c, 0) + 1); } //maintain a counter to check whether match the target string. int counter = map.size();//must be the map size, NOT the string size because the char may be duplicate. //Two Pointers: begin - left pointer of the window; end - right pointer of the window int begin = 0, end = 0; //the length of the substring which match the target string. int len = Integer.MAX_VALUE; //loop at the begining of the source string while(end < s.length()){ char c = s.charAt(end);//get a character if( map.containsKey(c) ){ map.put(c, map.get(c)-1);// plus or minus one if(map.get(c) == 0) counter--;//modify the counter according the requirement(different condition). } end++; //increase begin pointer to make it invalid/valid again while(counter == 0 /* counter condition. different question may have different condition */){ char tempc = s.charAt(begin);//***be careful here: choose the char at begin pointer, NOT the end pointer if(map.containsKey(tempc)){ map.put(tempc, map.get(tempc) + 1);//plus or minus one if(map.get(tempc) > 0) counter++;//modify the counter according the requirement(different condition). } /* save / update(min/max) the result if find a target*/ // result collections or result int value begin++; } } return result; } }该题的解法：
public class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> res = new ArrayList<>(); if(p.length()>s.length()) return res; HashMap<Character, Integer> map = new HashMap<>(); for(char c: p.toCharArray()) map.put(c,map.getOrDefault(c,0)+1); int diff = map.size(); int begin=0, end=0; while(end<s.length()){ char cur = s.charAt(end); if(map.containsKey(cur)){ map.put(cur,map.get(cur)-1); if(map.get(cur)==0) diff--; } end++; while(diff==0){ if(end-begin==p.length()) res.add(begin); char temp = s.charAt(begin); if(map.containsKey(temp)){ map.put(temp, map.get(temp)+1); if(map.get(temp)>0) diff++; } begin++; } } return res; } } https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/
