LeetCode LCR 014. 字符串的排列

约 5 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
字符串 哈希表 双指针 LCR 滑动窗口

题目描述

✅ LCR 014. 字符串的排列

image-20260928234829769

题意分析

判断 s2 中是否存在一个连续子串，恰好包含 s1 的全部字符及其出现次数，字符顺序可以任意变化。返回是否存在，不需要给出具体排列或出现位置。

排列不能增加或丢失字符，因此候选子串长度必须等于 s1 的长度。重复字符也要按次数匹配，仅比较出现过哪些字母不够。题目字符均为小写英文字母；若 s1 比 s2 长，直接无解。

解法：定长窗口比较字符频次

核心思路

[!blue]

两个等长字符串互为排列，当且仅当每一种字符的数量都相同。因此不用枚举排列，也不用排序各个子串，只需统计 s1 与候选窗口的字符频次。

设 m = s1.length()。cnt1 保存 s1 的固定频次，cnt2 保存 s2 中当前长度为 m 的窗口频次。小写字母只有二十六种，使用两个定长数组即可完整表达匹配条件。

先建立首个窗口 [0, m - 1] 并比较一次。随后右端移动到 i 时，加入 s2[i]、移除旧左端 s2[i - m]，更新后窗口为 [i - m + 1, i]。相邻窗口的其余字符完全相同，所以只修改这两个计数就能准确得到新频次，无需重新统计整段。

比较必须放在一进一出都完成之后，此时窗口长度才恰好为 m。所有频次相等便找到了一个排列，立即返回 true；起点逐格移动能覆盖全部等长子串，扫描结束仍无匹配就返回 false。

解题步骤

  1. 取得两串长度，若 m > n，直接返回 false，避免初始窗口越界。
  2. 统计 s1 全部字符与 s2 前 m 个字符的频次。
  3. 先比较初始两个频次数组，相等则返回 true。
  4. 从下标 m 开始移动右端，每次加入新字符并移除下标 i - m 的旧字符。
  5. 更新完整后比较频次，任意窗口匹配即可返回 true；否则最终返回 false。

代码实现

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();

        // 长度不够时不可能存在窗口，且能防止下面建表越界。
        if (m > n) {
            return false;
        }

        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];

        // 一趟填好 s1 的频次与 s2 的首个窗口。
        for (int i = 0; i < m; ++i) {
            ++cnt1[s1.charAt(i) - 'a'];
            ++cnt2[s2.charAt(i) - 'a'];
        }

        // 起点为 0 的窗口也是候选，不能漏比。
        if (Arrays.equals(cnt1, cnt2)) {
            return true;
        }

        for (int i = m; i < n; ++i) {
            // 右端进、左端出，两次修改后窗口长度重新回到 m。
            ++cnt2[s2.charAt(i) - 'a'];
            --cnt2[s2.charAt(i - m) - 'a'];

            if (Arrays.equals(cnt1, cnt2)) {
                return true;
            }
        }

        return false;
    }
}

func checkInclusion(s1 string, s2 string) bool {
    m, n := len(s1), len(s2)
    if m > n {
        return false
    }
    // 定长数组在 Go 里可直接用 == 比较，天然是值语义。
    var cnt1, cnt2 [26]int
    for i := 0; i < m; i++ {
        cnt1[s1[i]-'a']++
        cnt2[s2[i]-'a']++
    }
    if cnt1 == cnt2 {
        return true
    }
    for i := m; i < n; i++ {
        cnt2[s2[i]-'a']++
        cnt2[s2[i-m]-'a']--
        if cnt1 == cnt2 {
            return true
        }
    }
    return false
}

复杂度分析

  • 时间复杂度：O(m + 26n)，也就是 O(m + n)。初始统计为 O(m)，每次移动更新两个计数并比较固定二十六项。
  • 空间复杂度：O(1)。只使用两个固定长度的计数数组和少量下标。

关键点总结

[!green]

  • 排列匹配依赖字符频次相同，原来的字符顺序无需保留。
  • 目标长度固定，窗口只需同步一进一出，不需要按条件反复收缩。
  • 首窗口也属于候选，必须在开始移动前检查。
  • 本题只问存在性，首次命中即可结束。

易错点总结

[!yellow]

  • 只比较字符种类：相同字母可能出现多次，需求数量也必须一致。
  • 未判长度就建立首窗口：目标更长时会访问源串之外的位置。
  • 漏掉起点零：直接进入移动循环会跳过第一个候选，等长两串时尤其明显。
  • 移出下标写成 i - m + 1：这是新窗口左端，真正离开的是它前一位 i - m。
  • 加入后立即比较、还未移出旧字符：窗口临时包含 m + 1 个字符，不能用于判断等长排列。
  • Java 使用数组 == 比内容：应使用 Arrays.equals；Go 的定长数组可以直接比较。

相似题目

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