LeetCode 567. 字符串的排列

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 567. 字符串的排列

思路分析

参考代码

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

	var need [26]int   // 记录 s1 中每个字母出现的次数
	var window [26]int // 当前窗口中每个字母的出现次数

	for _, ch := range s1 {
		need[ch-'a']++
	}

	for i := 0; i < len(s2); i++ {
		window[s2[i]-'a']++

		// 如果窗口超过 s1 长度，则移除左侧字符
		if i >= len(s1) {
			window[s2[i-len(s1)]-'a']--
		}

		// 每次都判断当前窗口是否匹配
		if window == need {
			return true
		}
	}

	return false
}

时间复杂度：O(n)，其中 n 是 s2 的长度。

空间复杂度：O(1)，使用了两个长度为 26 的定长数组，与输入无关。

func checkInclusion(s1 string, s2 string) bool {
	// 如果 s1 长度大于 s2，直接返回 false
	if len(s1) > len(s2) {
		return false
	}

	// 创建频率数组来统计 s1 和 s2 中字符的出现次数
	s1Count := make([]int, 26)
	s2Count := make([]int, 26)

	// 统计 s1 中的字符频率
	for i := 0; i < len(s1); i++ {
		s1Count[s1[i]-'a']++
	}

	// 使用滑动窗口在 s2 中查找是否包含 s1 的排列
	for i := 0; i < len(s2); i++ {
		// 右指针扩展，增加当前字符的频率
		s2Count[s2[i]-'a']++

		// 如果窗口大小超过 s1 的长度，缩小窗口，减少左指针位置的字符频率
		if i >= len(s1) {
			s2Count[s2[i-len(s1)]-'a']--
		}

		// 每次检查窗口是否与 s1 的字符频率相等
		if equal(s1Count, s2Count) {
			return true
		}
	}

	return false
}

// 判断两个字符频率数组是否相等
func equal(arr1, arr2 []int) bool {
	for i := 0; i < 26; i++ {
		if arr1[i] != arr2[i] {
			return false
		}
	}
	return true
}

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/61267657