LeetCode 567. 字符串的排列

Categories:

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

题目描述

🔥 567. 字符串的排列

思路分析

如果s1的长度大于s2的长度，那么一定不可能包含s1的排列，直接返回false。

初始化两个映射：window和need。window用于存储s1中每个字符的频次，need用于存储滑动窗口中字符的频次。

使用双指针left和right来遍历s2。右指针不断扩展窗口，而左指针在窗口大小大于s1长度时右移。

在遍历过程中，维护need映射。当右指针扩展窗口时，增加相应字符的频次，当左指针右移时，减少相应字符的频次。如果字符频次减少到0，就从need映射中删除该字符。

如果need映射的长度等于window映射的长度，并且两个映射相等，说明找到了s2中的一个排列，返回true。

如果遍历完整个s2都没有找到满足条件的排列，返回false。

这个算法的时间复杂度是O(n)，其中N是s2的长度。在最坏情况下，左指针和右指针都会遍历整个s2字符串。

参考代码

func checkInclusion(s1 string, s2 string) bool {
	if len(s1) > len(s2) {
		return false
	}
	window := make(map[byte]int)
	for i := 0; i < len(s1); i++ {
		window[s1[i]]++
	}
	need := make(map[byte]int)
	left, right := 0, 0
	for right < len(s2) {
		need[s2[right]]++
		if right-left+1 > len(s1) {
			c := s2[left]
			need[c]--
			if need[c] == 0 {
				delete(need, c)
			}
			left++
		}
		if len(need) == len(window) {
			if reflect.DeepEqual(need, window) {
				return true
			}
		}
		right++
	}
	return false
}

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

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