字符串的排列

567. 字符串的排列

难度中等262收藏分享切换为英文接收动态反馈

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False

注意：

1. 输入的字符串只包含小写字母
2. 两个字符串的长度都在 [1, 10,000] 之间

暴力滑动窗口

class Solution {
   public boolean checkInclusion(String s1, String s2) {
        int[] hash = new int[26];
        int[] hashWindow = new int[26];
        int len = s1.length();

        for (int i = 0; i < len; i++) {
            hash[s1.charAt(i) - 'a']++;
        }

        int n = s2.length();
        int l = 0, r = 0;
        while (r < n) {
            hashWindow[s2.charAt(r) - 'a']++;
            if (r - l + 1 >= len) {
                if (r - l + 1 == len) {
                    if (judge(hash, hashWindow)) return true;
                }
                hashWindow[s2.charAt(l) - 'a']--;
                l++;
            }
            r++;
        }
        return false;
    }

    public boolean judge(int[] hash, int[] hashWindow) {
        for (int i = 0; i < 26; i++) {
            if (hashWindow[i] != 0 && hashWindow[i] != hash[i]) return false;
        }
        return true;
    }
}

优化滑动窗口

public class Solution {

    public boolean checkInclusion(String s1, String s2) {
        char[] pattern = s1.toCharArray();
        char[] text = s2.toCharArray();

        int pLen = s1.length();
        int tLen = s2.length();

        int[] pFreq = new int[26];
        int[] winFreq = new int[26];

        for (int i = 0; i < pLen; i++) {
            pFreq[pattern[i] - 'a']++;
        }

        int pCount = 0;// 记录字符的个数（去重）
        for (int i = 0; i < 26; i++) {
            if (pFreq[i] > 0){
                pCount++;
            }
        }

        int left = 0;
        int right = 0;
        // 当滑动窗口中的某个字符个数与 s1 中对应相等的时候才计数
        int winCount = 0;
        while (right < tLen){
            if (pFreq[text[right] - 'a'] > 0 ) {
                winFreq[text[right] - 'a']++;
                if (winFreq[text[right] - 'a'] == pFreq[text[right] - 'a']){
                    winCount++;// 记录窗口中字符的个数（去重）
                }
            }
            right++;
            
            while (pCount == winCount){// 去重后的字符种类相同
                if (right - left == pLen){// 数量也相同
                    return true;
                }
                if (pFreq[text[left] - 'a'] > 0 ) {// 左边界收缩
                    winFreq[text[left] - 'a']--;
                    if (winFreq[text[left] - 'a'] < pFreq[text[left] - 'a']){// 如果不相等了去掉这个种类
                        winCount--;// 种类减1
                    }
                }
                left++;
            }
        }
        return false;
    }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/permutation-in-string/solution/zi-fu-chuan-de-pai-lie-by-leetcode-q6tp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信