侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【滑动窗口】字符串的排列

GabrielxD
2022-10-18 / 0 评论 / 0 点赞 / 11 阅读 / 472 字 / 正在检测是否收录...

题目

567. 字符串的排列

剑指 Offer II 014. 字符串中的变位词


给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false

换句话说,s1 的排列之一是 s2子串

示例 1:

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

示例 2:

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

提示:

  • 1 <= s1.length, s2.length <= 10^4
  • s1s2 仅包含小写字母

解题

方法一:暴力 枚举

思路

暴力枚举 s2 中所有长度为 s1.length() 的子字符串并判断其与 s2 的字符组成是否相同。

代码

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] targetCnts = new int[26];
        for (char ch : s1.toCharArray()) ++targetCnts[ch - 'a']; 
        char[] chs = s2.toCharArray();
        int n1 = s1.length(), n2 = chs.length;
        int[] cnts = new int[26];
        outer: for (int i = 0; i <= n2 - n1; ++i) {
            Arrays.fill(cnts, 0);
            for (int j = i; j < i + n1; ++j) {
                int idx = chs[j] - 'a';
                if (++cnts[idx] > targetCnts[idx]) continue outer;
            }
            return true;
        }
        return false;
    }
}

方法二:滑动窗口

思路

【哈希表, 滑动窗口】最小覆盖子串的滑窗有异曲同工之妙,只不过窗口几乎变成了固定长度,所以在左指针增加时不用循环,只需要判断窗口大小是否等于 s1 的长度就行了。

代码

class Solution {
    static final int HASH_LEN = 'z' + 1;

    public boolean checkInclusion(String s1, String s2) {
        int[] require = new int[HASH_LEN], window = new int[HASH_LEN];
        int target = 0;
        for (char ch : s1.toCharArray()) {
            if (++require[ch] == 1) ++target;
        }
        char[] chs = s2.toCharArray();
        int m = s1.length(), n = chs.length;
        int left = 0, right = 0, valid = 0;
        while (right < n) {
            int idx = chs[right++];
            if (++window[idx] == require[idx]) ++valid;
            if (right - left >= m) {
                if (valid == target) return true;
                idx = chs[left++];
                if (window[idx]-- == require[idx]) --valid;
            }
        }
        return false;
    }
}
0

评论区