“This is the 17 days THAT I have participated in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021.”

Given two strings s1 and s2, write a function to determine whether S2 contains an anagram of s1.

In other words, one of the permutations of the first string is a substring of the second string.

 

Example 1: Input: s1 = "ab" s2 = "eidbaooo" Output: True Explanation: S2 contains one of the permutations of s1 ("ba"). Example 2: Input: s1= "ab" s2 = "eidboaoo" Output: False Warning: 1 <= s1.length, s2.length <= 104 S1 and s2 contain only lowercase lettersCopy the code

Source: LeetCode link: leetcode-cn.com/problems/MP…

Train of thought

  • First of all, the topic of heterotopic words can generally be solved in space for time
    • So we can use hash tables to do that
    • But they say it’s lowercase, so we’re going to use a fixed size26Bit array to mark count
  • We useabandcbaFor example

    • When there are such examples as AB and ABC, we are the best solution

    • Ab is a subsequence of ABC by adding and subtracting the corresponding position in the array

    • So the first judgment in our code is to make a case like this

    • In the case of AB and CBA, we use the double pointer to solve the problem

    • So we start with the following situation

  • And then corresponding to the string2The situation is shown below

  • wills1The string is the length of the sliding window, scanned each time

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        boolean flag = true;
         if (s2.length() < s1.length()) {
             return false;
         }
         int[] counts = new int[26];
         for (int i = 0; i < s1.length(); i++) {
             counts[s1.charAt(i) - 'a'] + +; counts[s2.charAt(i) -'a']--;
         }
         if (check(counts)) return true;

         for (int i = s1.length(); i < s2.length(); i++) {
             counts[s2.charAt(i) - 'a']--;
             counts[s2.charAt(i - s1.length()) - 'a'] + +;if (check(counts)) return true;
         }
        
         return false;      
    }
    boolean check(int[] arr) {
        for (int i : arr) {
            if(i ! =0) return false;
        }
        return true; }}Copy the code

In the next article, we will introduce variations of this problem. This article mainly uses the double pointer + notation method 📌