LeetCode 438. Find all letter ectopic words in the string__ sliding window

438. Find all alphabetic words in the string

Given two strings s and p, find s All in p Of Heterotopic words The string of , Returns the starting index of these substrings . Regardless of the order of the answer output .

Heterotopic words A string formed by rearrangement of the same letters （ Include the same string ）.

 Example  1:

 Input : s = "cbaebabacd", p = "abc"
 Output : [0,6]
 explain :
 Start index equals  0  The substring is  "cba",  It is  "abc"  The heterotopic words of .
 Start index equals  6  The substring is  "bac",  It is  "abc"  The heterotopic words of .
  Example  2:

 Input : s = "abab", p = "ab"
 Output : [0,1,2]
 explain :
 Start index equals  0  The substring is  "ab",  It is  "ab"  The heterotopic words of .
 Start index equals  1  The substring is  "ba",  It is  "ab"  The heterotopic words of .
 Start index equals  2  The substring is  "ab",  It is  "ab"  The heterotopic words of .
 

 Tips :

1 <= s.length, p.length <= 3 * 104
s  and  p  Only lowercase letters 

Solution1( Straight sliding window ):

Obviously, we can use sliding window to solve this problem , Direct maintenance p String length window , When the window is full, judge whether the number of letters in the window is the same as p The consistency of the .

Code1:

class Solution {
    
    public List<Integer> findAnagrams(String s, String p) {
    
        int[] hash = new int[26];
        int winLen = p.length();
        for(int i=0;i<winLen;i++){
    
            char c = p.charAt(i);
            hash[c - 'a']++;
        }

        List<Integer> res = new ArrayList<>();
        List<Integer> window = new ArrayList<>();
        for(int i=0;i<s.length();i++){
    
            char c = s.charAt(i);
            if(window.size() < winLen){
    
                window.add(i);
            }
            else{
    
                check(res,winLen,window,hash,s);
                window.remove((int)0);
                i--;
            }
        }
        if(window.size() < winLen){
    
            return res;
        }
        check(res,winLen,window,hash,s);
        return res;
    }

    public void check(List<Integer> res,int winLen,List<Integer> window,int[] hash,String s){
    
        int[] hashTemp = new int[26];
        for(int k=0;k<winLen;k++){
    
            Integer index = window.get(k);
            hashTemp[s.charAt(index) - 'a']++;
        }
        int j = 0;
        for(;j<26;j++){
    
            if(hash[j] != hashTemp[j])
                break;
        }
        if(j == 26){
    
            res.add(window.get(0));
        }
    }
}

Solution2( Optimize convenient sliding window ):

We can not directly maintain ordinary sliding windows , Because we found the above method one , Because it is to maintain an ordered sequence to simulate sliding windows , A hash array is also needed to indicate the type and number of letters contained in the sliding window , So we can just create a hash array once , When sliding out the old element and sliding in the new element, you can directly modify the hash array .
Then we found , You can directly use a hash array instead of an ordered sequence of sliding windows for storage , Just use two subscripts to simulate sliding window , The sliding window itself does not need to store content , Just give it to the hash array for storage .

Code2:

class Solution {
    
    public List<Integer> findAnagrams(String s, String p) {
    
        int slen = s.length();
        int plen = p.length();

        List<Integer> res = new ArrayList<>();
        if(s.length() < p.length()){
    
            return res;
        }
        
        int[] hash = new int[26];
        int[] hashTemp = new int[26];
        //  Fill the sliding window first 
        for(int i=0;i<plen;i++){
    
            hash[p.charAt(i) - 'a']++;
            hashTemp[s.charAt(i) - 'a']++;
        }

        if(Arrays.equals(hash,hashTemp)){
    
            res.add(0);
        }

		//  Maintain the two subscripts of the sliding window , A head , A head + The length of sliding window is enough 
        for(int i=0;i<slen - plen ;i++){
    
            hashTemp[s.charAt(i) - 'a']--;
            hashTemp[s.charAt(i + plen) - 'a']++;
            if(Arrays.equals(hash,hashTemp)){
    
                res.add(i+1);
            }
        }

        return res;
    }
}