The finger of the sword Offer II 015. All modifiers in the string

One 、 subject

Original link ： The finger of the sword Offer II 015. All modifiers in the string

1. Title Description

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

A modifier Means the same letters , But arrange different strings .

Example 1:

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

Example 2:

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

Tips :

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

Be careful ： This topic and the main station 438 The question is the same ： https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

2. Basic framework

C++ The basic framework code is as follows :

vector<int> findAnagrams(string s, string p) {
    
}

3. Their thinking

• Topic analysis

1. The goal of the topic is to return the starting subscript of all the modified word substrings .
2. An anagram string is a string in which the number of elements is the same and the type is the same , Strings in different order .
3. Define two sets of hash arrays s_rec and q_rec, among s_rec The function of array as a sliding window record element . If the current sliding window array s_rec be equal to q_rec Array , Then it means that the substring in the current sliding window is Anagram string .
4. Move the sliding window to the right every time , Just move out the element on the left side of the window , Move a new element to the right of the window . The corresponding operation is that the elements on the left side of the window are s_rec Subtract one from the position of the index in , The new element on the right is s_rec Add one to the position of the index in .
5. If you find an anagram string , Then the leftmost element of the sliding window is taken as the starting position of the substring , Store in res Array , When the traversal is over , return res Array ,res The array represents s The starting position of all modifier substrings in the string .

• Implementation code ：

  vector<int> findAnagrams(string s, string p) {
        
      if (s.length() < p.length()) return {
        };	//  There is no modifier string 
      vector<int> s_rec(26, 0);
      vector<int> p_rec(26, 0);
      vector<int> res;
      int len = p.size();
      int i;
      for (i = 0; i < p.size(); i++)
      {
        
          ++s_rec[s[i] - 'a'];
          ++p_rec[p[i] - 'a'];
      }
      if (s_rec == p_rec) res.push_back(0); //  With 0 For the starting node s Whether the substring is an anagram string 
      for (i = 1; i < s.size() - len + 1; i++)
      {
        
          --s_rec[s[i - 1] - 'a'];
          ++s_rec[s[i + len - 1] - 'a'];
          if (s_rec == p_rec)	//  Whether the current sliding window is an anagram string 
              res.push_back(i);
      }
      return res;
  }
  

Two 、 Summary of knowledge points

   This time we use $hash$ and The sliding window , Every time you slide a window, you subtract one element from the left , Add an element on the right , It is no longer necessary to re count the middle elements in the window , Thus reducing the number of operations .