LeetCode 567. 字符串的排列

约 4 分钟
文章信息 12 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 20-50 腾讯 字节 微软 拼多多 京东 B站
标签
字符串 哈希表 双指针 滑动窗口

题目描述

✅ 567. 字符串的排列

image-20260928201335193

题意分析

判断 s2 中是否存在一段连续子串，能由 s1 的全部字符重新排列得到，只需返回是否存在。

排列可以改变顺序，但不能改变长度和每种字符的数量。因此，候选子串必须与 s1 等长，且各字母出现次数完全相同；分散在不同位置的字符不能拼成候选。题目只包含小写英文字母，可以用 26 个计数记录频次。

解法：固定长度滑动窗口计数

核心思路

[!blue]

令 m 为 s1 的长度。所有可能答案都是 s2 中长度为 m 的窗口，不必真的生成 s1 的排列。对等长字符串，只要 26 个字母的频次逐项相等，就能将其中一个重排成另一个。

先用 target 保存 s1 的频次，再用 window 保存当前窗口的频次。相邻窗口只有一个字符进入、一个字符离开，其余字符不变，因此移动窗口只需更新这两个计数。

扫描到右端 right 时，先加入 s2[right]。如果已经超过 m 个字符，就移除下标 right - m 的字符。更新后，window 精确对应区间 [max(0, right - m + 1), right]。前几个窗口可能还没满，只有 right >= m - 1 时才比较频次。

每个长度为 m 的连续子串都会恰好成为一次窗口；发现频次相等即可返回 true，全部窗口都不匹配才返回 false。

解题步骤

  1. 若 s1 比 s2 长，不存在足够长的子串，直接返回 false。
  2. 统计 s1 的字母频次，保存到 target；将 window 初始化为全零。
  3. 从左到右扫描 s2，将右端字符的计数加一。
  4. 若 right >= m，将 s2[right - m] 的计数减一，使窗口长度至多为 m。
  5. 窗口满长后比较两个数组；完全相等就返回 true，遍历结束仍未命中则返回 false。

代码实现

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

        int[] target = new int[26];
        int[] window = new int[26];

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

        for (int right = 0; right < s2.length(); right++) {
            window[s2.charAt(right) - 'a']++;

            // 超出固定长度后才移出旧字符，首次满窗时还不需要移出。
            if (right >= s1.length()) {
                window[s2.charAt(right - s1.length()) - 'a']--;
            }

            // 长度已经足够且频次相同，才是一个完整排列窗口。
            if (right >= s1.length() - 1 && Arrays.equals(target, window)) {
                return true;
            }
        }

        return false;
    }
}

func checkInclusion(s1 string, s2 string) bool {
    if len(s1) > len(s2) {
        return false
    }

    var target, window [26]int
    for i := 0; i < len(s1); i++ {
        target[s1[i]-'a']++
    }

    for right := 0; right < len(s2); right++ {
        window[s2[right]-'a']++
        // 超出固定长度后才移出旧字符，首次满窗时还不需要移出。
        if right >= len(s1) {
            window[s2[right-len(s1)]-'a']--
        }
        // 长度已经足够且频次相同，才是一个完整排列窗口。
        if right >= len(s1)-1 && window == target {
            return true
        }
    }
    return false
}

复杂度分析

  • 时间复杂度：$O(m+n)$，其中 $m$、$n$ 分别为两个字符串的长度。目标计数耗时 $O(m)$，每次滑动做常数次更新并比较 26 项，全部窗口共耗时 $O(n)$。
  • 空间复杂度：$O(1)$，只使用两个长度固定为 26 的计数数组。

关键点总结

[!green]

  • 排列匹配转化为频次匹配，避免枚举排列或对子串反复排序。
  • 长度固定后，窗口每右移一格，只更新移入和移出的字符。
  • 更新完成时，计数数组必须与当前窗口一一对应；判断相等之前还要确认窗口已满。

易错点总结

[!yellow]

  • 首个完整窗口在 right == m - 1 时就应检查；推迟到 right == m 会漏掉开头的答案。
  • 加入新字符后移出的下标是 right - m，不是 right - m + 1；后者仍属于新窗口。
  • 只比较字符种类无法处理重复字符，必须逐项比较出现次数。
  • 子串要求连续，不能用子序列的匹配方式跳过中间字符。
  • 每次重新统计整个窗口会产生 $O(nm)$ 的重复工作；应保留并更新已有计数。

相似题目

题目 难度 关联与区别
438. 找到字符串中所有字母异位词 中等 窗口匹配条件相同，原题收集全部起点，本题找到一处即可返回true。
76. 最小覆盖子串 困难 同样统计窗口字符，原题只需覆盖目标且允许更长窗口，本题要求长度及频次恰好相同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/61267657
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！