LeetCode 567. 字符串的排列
题目描述
思路分析
解法一：固定长度滑动窗口 + 频次数组比较（推荐）
核心思路：
- s1 的任意排列长度固定为
s1.length()，因此在 s2 中枚举的窗口长度也固定为该值。- 维护两个长度为 26 的字符频次数组：
need统计 s1 各字符出现次数，window统计当前窗口各字符出现次数。- 滑动窗口每向右移动一步，右侧新增字符计数 +1，左侧移出字符计数 -1，然后直接比较两个数组是否相等。
- Go 中数组是值类型，可以直接用
==比较两个[26]int，效率极高。
复杂度分析：
- 时间复杂度：O(n + 26·n) = O(n)，其中 n 表示 s2 的长度，每次窗口滑动后比较两个长度为 26 的数组耗时 O(26) 为常数。
- 空间复杂度：O(1)，使用两个长度为 26 的固定大小数组，与输入规模无关。
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) {
return false;
}
// 统计 s1 各字符频次
int[] need = new int[26];
// 统计当前滑动窗口各字符频次
int[] window = new int[26];
for (char c : s1.toCharArray()) {
need[c - 'a']++;
}
int k = s1.length();
for (int i = 0; i < s2.length(); i++) {
// 右侧新字符入窗口
window[s2.charAt(i) - 'a']++;
// 窗口超过固定长度时，移除最左侧字符
if (i >= k) {
window[s2.charAt(i - k) - 'a']--;
}
// 窗口达到目标长度后，比较频次数组
if (i >= k - 1 && Arrays.equals(window, need)) {
return true;
}
}
return false;
}
}
func checkInclusion(s1 string, s2 string) bool {
if len(s1) > len(s2) {
return false
}
// 统计 s1 各字符频次
var need [26]int
// 统计当前滑动窗口各字符频次
var window [26]int
for _, ch := range s1 {
need[ch-'a']++
}
k := len(s1)
for i := 0; i < len(s2); i++ {
// 右侧新字符入窗口
window[s2[i]-'a']++
// 窗口超过固定长度时，移除最左侧字符
if i >= k {
window[s2[i-k]-'a']--
}
// Go 数组可直接用 == 比较，窗口达到目标长度后判断是否匹配
if i >= k-1 && window == need {
return true
}
}
return false
}
解法二：滑动窗口 + diff 计数器优化
核心思路：
- 在解法一基础上进一步优化：不再每次全量比较两个频次数组，而是维护一个
diff变量记录当前窗口与 s1 频次不相等的字符种数。- 初始化时，将 s2 前
k个字符与 s1 逐一比对建立初始diff。- 每次窗口右移时，仅更新右侧新增字符和左侧移除字符对
diff的贡献，时间为严格 O(1)。- 当
diff == 0时，说明窗口内字符频次与 s1 完全一致，即找到了一个排列。
复杂度分析：
- 时间复杂度：O(n)，其中 n 表示 s2 的长度，每次滑动窗口更新 diff 为严格 O(1)，整体线性。
- 空间复杂度：O(1)，使用长度为 26 的固定数组及若干辅助变量。
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) {
return false;
}
// cnt[i] = need[i] - window[i]，正数表示还缺该字符，负数表示多余
int[] cnt = new int[26];
for (char c : s1.toCharArray()) {
cnt[c - 'a']++;
}
int k = s1.length();
// diff 记录 cnt 中不为 0 的字符种数
int diff = 0;
// 初始化前 k 个字符的窗口
for (int i = 0; i < k; i++) {
int idx = s2.charAt(i) - 'a';
// 将该字符从 cnt 中扣除，若扣除前为 0 则 diff 增加，扣除后为 0 则 diff 减少
if (cnt[idx] == 0) {
diff++;
}
cnt[idx]--;
if (cnt[idx] == 0) {
diff--;
}
}
if (diff == 0) {
return true;
}
// 滑动窗口向右扩展
for (int i = k; i < s2.length(); i++) {
// 右侧新字符入窗口
int right = s2.charAt(i) - 'a';
if (cnt[right] == 0) {
diff++;
}
cnt[right]--;
if (cnt[right] == 0) {
diff--;
}
// 左侧旧字符出窗口
int left = s2.charAt(i - k) - 'a';
if (cnt[left] == 0) {
diff++;
}
cnt[left]++;
if (cnt[left] == 0) {
diff--;
}
if (diff == 0) {
return true;
}
}
return false;
}
}
func checkInclusion(s1 string, s2 string) bool {
if len(s1) > len(s2) {
return false
}
// cnt[i] = need[i] - window[i]，正数表示还缺该字符，负数表示多余
var cnt [26]int
for _, ch := range s1 {
cnt[ch-'a']++
}
k := len(s1)
// diff 记录 cnt 中不为 0 的字符种数
diff := 0
// 初始化前 k 个字符的窗口
for i := 0; i < k; i++ {
idx := s2[i] - 'a'
// 扣除前为 0 则 diff 增加，扣除后为 0 则 diff 减少
if cnt[idx] == 0 {
diff++
}
cnt[idx]--
if cnt[idx] == 0 {
diff--
}
}
if diff == 0 {
return true
}
// 滑动窗口向右扩展
for i := k; i < len(s2); i++ {
// 右侧新字符入窗口
right := s2[i] - 'a'
if cnt[right] == 0 {
diff++
}
cnt[right]--
if cnt[right] == 0 {
diff--
}
// 左侧旧字符出窗口
left := s2[i-k] - 'a'
if cnt[left] == 0 {
diff++
}
cnt[left]++
if cnt[left] == 0 {
diff--
}
if diff == 0 {
return true
}
}
return false
}
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 438. 找到字符串中所有字母异位词 | 中等 | 滑动窗口 / 固定窗口 |
| 76. 最小覆盖子串 | 困难 | 滑动窗口 / 哈希表 |
| 3. 无重复字符的最长子串 | 中等 | 滑动窗口 / 哈希表 |
| 424. 替换后的最长重复字符 | 中等 | 滑动窗口 / 频率统计 |
| 904. 水果成篮 | 中等 | 滑动窗口 / 哈希表 |
| 187. 重复的DNA序列 | 中等 | 哈希表 / 滑动窗口 |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！