567. Permutation in String

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given two strings s1 and s2, return true if s2 contains the permutation of s1.

In other words, one of s1’s permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

• $1 <= s1.length, s2.length <= 10^4$
• s1 and s2 consist of lowercase English letters.

Code

438. Find All Anagrams in a String

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;

        int[] dict1 = new int[26];
        int[] dict2 = new int[26];
        
        for (int i = 0; i < s1.length(); i++) {
            dict1[s1.charAt(i) - 'a']++;
            dict2[s2.charAt(i) - 'a']++;
        }

        if (helper(dict1, dict2)) return true;

        for (int i = 1; i <= s2.length() - s1.length(); i++) {
            dict2[s2.charAt(i - 1) - 'a']--;
            dict2[s2.charAt(i + s1.length() - 1) - 'a']++;

            if (helper(dict1, dict2)) return true;
        }

        return false;
    }

    public boolean helper(int[] dict1, int[] dict2) {
        for (int i = 0; i < 26; i++) {
            if (dict1[i] != dict2[i]) return false;
        }
        
        return true;
    }
}

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;

        int[] dict1 = new int[26];
        int[] dict2 = new int[26];
        
        for (int i = 0; i < s1.length(); i++) {
            dict1[s1.charAt(i) - 'a']++;
            dict2[s2.charAt(i) - 'a']++;
        }

        int count = 0;
        
        for (int i = 0; i < 26; i++) {
            if (dict1[i] == dict2[i])
                count++;
        }
        
        if(count == 26) return true;

        for (int i = 1; i <= s2.length() - s1.length(); i++) {
            int left = s2.charAt(i - 1) - 'a';
            int right = s2.charAt(i + s1.length() - 1) - 'a';


            dict2[right]++;
            
            if (dict2[right] == dict1[right]) {
                count++;
            } else if (dict2[right] == dict1[right] + 1) {
                count--;
            }
            
            dict2[left]--;
            
            if (dict2[left] == dict1[left]) {
                count++;
            } else if (dict2[left] == dict1[left] - 1) {
                count--;
            }
            
            if (count == 26) return true;
        }

        return false;
    }
}