LeetCode 567. 字符串的排列

约 5 分钟
文章信息 12 个分类 5 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 20-50 字节跳动 微软 腾讯 京东 拼多多 哔哩哔哩
标签
字符串 哈希表 双指针 滑动窗口 滑动窗口经典题
目录

题目描述

✅ 567. 字符串的排列

image-20231022234655952

题意分析

问的是 s2 中是否存在一个连续子串，它恰好是 s1 的某个排列。这里有两个容易被读漏的限定：一是子串必须连续，不是子序列；二是「排列」意味着长度必须与 s1 完全相同，多一个字符少一个字符都不算。

排列这个词是关键的约束信号。两个字符串互为排列，充要条件是它们每个字符的出现次数完全一致，字符的先后顺序不产生任何影响。既然候选子串的长度被钉死为 s1 的长度，那么待检验的对象就只有 s2 中长度固定的那些连续片段，数量是 $\lvert s2\rvert - \lvert s1\rvert + 1$ 个，问题变成对这批片段逐一做频次比对。

输入只含小写字母，字符集大小恒为 26，这暗示可以用定长数组代替哈希表来记录频次。长度上限在万级，允许线性或接近线性的做法。边界方面：s1 比 s2 长时不可能存在答案，必须先行拦截，否则窗口永远凑不满；两串长度相等时唯一的候选就是 s2 本身。返回值是布尔量，找到一个即可停止，不需要枚举全部。

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

核心思路

排列只关心字符出现次数，而合法子串的长度固定为 s1.length()，因此用定长滑动窗口枚举 s2 的所有候选子串。若对每个候选重新排序或计数，会反复处理相邻窗口的公共部分；窗口右移时只需加入一个字符、移出一个字符。

用 target[26] 保存 s1 的频次，window[26] 保存当前窗口的频次。循环不变量是：处理完右端点 right 后，window 精确对应长度不超过 s1.length()、以 right 结尾的后缀窗口。先加入 s2[right]，再在窗口超长时移出 s2[right - s1.length()]，即可维持该不变量。

当窗口长度达到 s1.length() 且两个频次数组相等时，窗口子串与 s1 长度相同、字符多重集合也相同，所以它必然是 s1 的一个排列；反之，任何排列都会在对应窗口被检出。

解题步骤

  1. 若 s1.length() > s2.length()，直接返回 false，因为 s2 无法提供一个足够长的窗口。
  2. 统计 s1 的 26 个字母频次，作为目标计数。
  3. 令 right 从左到右扫描 s2：先把 s2[right] 加入窗口；若 right >= s1.length()，再移出 s2[right - s1.length()]。
  4. 窗口凑满后比较两个频次数组，相等就返回 true；全部窗口都不匹配则返回 false。

例如 s1 = "ab"、s2 = "eidbaooo"，长度为 2 的窗口依次是 "ei"、"id"、"db"、"ba"。滑到 "ba" 时，a 和 b 的计数都与 s1 相同，因此返回 true。

代码实现

import java.util.Arrays;

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$ 分别是 s1、s2 的长度。每个窗口比较 26 个计数，字母表大小为常数。
  • 空间复杂度：$O(1)$，两个计数数组的长度固定为 26；若字符集大小记为 $\lvert\Sigma\rvert$，则为 $O(\lvert\Sigma\rvert)$。

关键点总结

  • 「排列 / 异位词」的判定本质是等长字符串的频次相等。
  • 候选长度固定时使用定长窗口；窗口右移只更新进出的两个字符。
  • 不变量是 window 始终对应当前合法窗口，判定前还必须确认窗口已经凑满。
  • 面试若追问常数优化，可维护频次已相等的字母数；但 26 位数组直接比较更简洁、更难写错。

易错点总结

  • 判定窗口成型的阈值是 right >= s1.length() - 1。若写成 right >= s1.length()，s1 = "ab"、s2 = "ba" 会漏解。
  • 加入新字符后，应移出的下标是 right - s1.length()。多加 1 会删掉仍在窗口内的字符，破坏计数不变量。
  • 只比较字符种类不够：s1 = "aab"、窗口 "abb" 的种类相同，但次数不同。
  • 不能把题目当成子序列匹配。s1 = "ab"、s2 = "acb" 能按顺序找到 a、b，却没有长度为 2 的匹配子串。
  • 每个窗口重新计数会退化为 $O(nm)$；滑动窗口的价值正是复用相邻窗口的共享部分。

相似题目

题目 难度 考察点
438. 找到字符串中所有字母异位词 中等 同一模型但要收集全部起点，命中后不能短路返回
LCR 014. 字符串的排列 中等 与本题同题，可用来练习 matched 计数器的 $O(n)$ 写法
LCR 015. 找到字符串中所有字母异位词 中等 438 同题，重点在结果列表的下标记录方式
76. 最小覆盖子串 困难 窗口长度不再固定，需要伸缩双指针并维护「已满足」计数
3. 无重复字符的最长子串 中等 可变长窗口的另一形态，收缩条件由重复字符而非计数触发