Sword finger offer II 014. anagrams in strings

The finger of the sword Offer II 014. An anamorphic word in a string

subject

Given two strings s1 and s2, Write a function to judge s2 Does it include s1 An anamorphic word of .

let me put it another way , One of the permutations of the first string is the... Of the second string Substring .

Example 1：

 Input : s1 = "ab" s2 = "eidbaooo"
 Output : True
 explain : s2  contain  s1  One of the permutations of  ("ba").

Example 2：

 Input : s1= "ab" s2 = "eidboaoo"
 Output : False

Tips ：

1 <= s1.length, s2.length <= 104
s1 and s2 Only lowercase letters

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/MPnaiL
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Answer key

Concerns
1.s1 Which characters have appeared in
2.s1 After random combination of characters , stay s2 Need to appear continuously in

We're traversing s1 When , Can be s1 The characters that have appeared are stored in map in .key Character ,value Is the number of occurrences . All lowercase letters here can also be used 26 Bit array implementation .
Traverse s2, Assume that the coordinates are i, So at this time [i,i+s1.length-1] It should all be in s1 There have been . This will ensure continuity .
How to compare [i,i+s1.length-1] and s1 Whether the array of is the same ？ You can give s2 Also create an array , Record the elements and number that have appeared in the window .

var checkInclusion = function(s1, s2) {
    
 	let s1Arr=new Array(26).fill(0);
 	let s2Arr=new Array(26).fill(0);
    if(s2.length<s1.length)return false;	
    for(let ch of s1){
     // Record s1 The situation of 
        s1Arr[ch.charCodeAt()-'a'.charCodeAt()]++;
    }
    let left = 0;
    for(let right = 0; right < s2.length; right ++) {
    
        s2Arr[s2[right].charCodeAt() - 'a'.charCodeAt(0)] ++; 
        if(right - left + 1 === s1.length) {
     // When the window size is just right , Compare whether the elements inside are equal 
            if(s1Arr.toString() === s2Arr.toString()) return true  
        }

        if(right >= s1.length - 1) {
     // If the window size exceeds , It means you need to start shrinking 
            s2Arr[s2[left].charCodeAt() - 'a'.charCodeAt()]--;
            left ++;
        }
    }
    return false;
};