# 438. Find All Anagrams in a String

###### tags: `leetcode`,`anagram`,`medium`

>ref: https://leetcode.com/problems/find-all-anagrams-in-a-string/
>
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

>Constraints:

### brute force

>1. spatialCom O(26\*2); timeCom (s.len()\*t.len())
>2. 用count 去判斷是否為anagram

    public List<Integer> findAnagrams(String s, String p) {
        
        List<Integer> ans= new LinkedList<>();
        
        int[] record= new int[26];
        
        //準備模板比較
        for(int i=0;i<p.length();i++){
            record[p.charAt(i)-97]++;
        }
        
        int[] tmp= new int[26]; //扣減用
        
        for(int j=0;j<=s.length()-p.length();j++){
            
            int count=p.length();
            
            tmpRollBack(record,tmp); //重置temp
            
            for(int k=j;k<j+p.length();k++){
                tmp[s.charAt(k)-97]--;
                if(tmp[s.charAt(k)-97]<0){
                    if(record[s.charAt(k)-97]==0){
                        j=k;//如果是沒出現過的字 next run 從此開始
                    }
                    break;
                }else{
                    count--;
                }
            }
            
            if(count==0){
                ans.add(j); //完全扣減為0時是解
            }
        }
        
        return ans;
        
        
    }
    

    //複製record到tmp中
    private void tmpRollBack(int[] record, int[] tmp){
        
        for(int i=0;i<record.length;i++){
            tmp[i]=record[i];
        }
        
    }

### slide window

>1. spatialCom O(26); timeCom (s.len)
>2. 用count 去判斷是否為anagram; 如果是樣板文字char之一 record[s.charAt(right)-'a']>=1 其他例外文字則會<=0 , 回填count數量時 當填補前 record[s.charAt(left)-'a']>=0時表示已經為樣板文字 (例外文字record[s.charAt(left)-'a']再填補前<0)

    public List<Integer> findAnagrams(String s, String p) {
        
        List<Integer> ans= new LinkedList<>();
        
        int[] record= new int[26];
        
        for(int i=0;i<p.length();i++){
            record[p.charAt(i)-97]++;
        }
        
        int count=p.length();
        int left=0;
        int right=0;
        
        while(right<s.length()){

            if( record[s.charAt(right)-'a']>=1 ){ 
                //>=1 為足量的 t 樣板文字
                count--;
            }
                record[s.charAt(right)-'a']--;  
                right++;

            if(count==0){
                ans.add(left);
            }

            if(right-left==p.length()){  //差異為p長度時開始回填 sliding window
                if(record[s.charAt(left)-'a']>=0){
                    //只有樣板文字有機會再填補前>=0 例外文字會<0 因為先被扣減了
                    count++; 
                }
                record[s.charAt(left)-'a']++;
                left++;
            }
        }
        
        return ans;
    }

可整理如下

    public List<Integer> findAnagrams(String s, String p) {
        
        List<Integer> ans= new LinkedList<>();
        
        int[] record= new int[26];
        
        for(int i=0;i<p.length();i++){
            record[p.charAt(i)-97]++;
        }
        
        int count=p.length();
        int left=0;
        int right=0;
        
        while(right<s.length()){

            if( record[s.charAt(right++)-'a']-->=1 ){
                count--;
            }
            if(count==0){
                ans.add(left);
            }
            if(right-left==p.length() &&  record[s.charAt(left++)-'a']++>=0 ){
                    count++;
            }
        }
        return ans;
    }