LeetCode 题解工作台
字符串的排列
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的 排列 。如果是，返回 true ；否则，返回 false 。 换句话说， s1 的排列之一是 s2 的 子串 。 示例 1： 输入： s1 = "ab" s2 = "eidbaooo" 输出： true 解释： s2 包含…
4
题型
7
代码语言
3
相关题
当前训练重点
中等 · 双·指针·invariant
答案摘要
我们用一个数组 记录当前需要匹配的字符及其个数，用一个变量 记录当前还需要匹配的字符种类数，初始时 为字符串 中各字符出现次数，而 为 中不同字符的个数。 然后我们遍历字符串 ，对于每个字符，我们将其在 中的对应值减一，如果减一后的值等于 ，说明当前字符在 中出现次数已经满足要求，我们将 减一。如果当前下标 大于等于 的长度，我们需要将 中对应值加一，如果加一后的值等于 ，…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的 排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
示例 2：
输入：s1= "ab" s2 = "eidboaoo" 输出：false
提示：
1 <= s1.length, s2.length <= 104s1和s2仅包含小写字母
解题思路
方法一：滑动窗口
我们用一个数组 记录当前需要匹配的字符及其个数，用一个变量 记录当前还需要匹配的字符种类数，初始时 为字符串 中各字符出现次数，而 为 中不同字符的个数。
然后我们遍历字符串 ，对于每个字符，我们将其在 中的对应值减一，如果减一后的值等于 ，说明当前字符在 中出现次数已经满足要求，我们将 减一。如果当前下标 大于等于 的长度，我们需要将 中对应值加一，如果加一后的值等于 ，说明当前字符在 中出现次数不再满足要求，我们将 加一。在遍历过程中，如果 的值等于 ，说明所有字符的出现次数都满足要求，我们就找到了一个满足要求的子串，返回 。
否则，如果遍历结束后没有找到满足要求的子串，我们返回 。
时间复杂度 ，其中 和 分别是字符串 和 的长度。空间复杂度 ，其中 是字符集，这道题中字符集为小写字母，所以空间复杂度是常数级别的。
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
cnt = Counter(s1)
need = len(cnt)
m = len(s1)
for i, c in enumerate(s2):
cnt[c] -= 1
if cnt[c] == 0:
need -= 1
if i >= m:
cnt[s2[i - m]] += 1
if cnt[s2[i - m]] == 1:
need += 1
if need == 0:
return True
return False
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(l_1 + (l_2 - l_1)) \approx O(l_2) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Can the candidate optimize the brute force approach?
- question_mark
Does the candidate demonstrate understanding of sliding window and hash table concepts?
- question_mark
Is the candidate able to explain the time complexity and avoid redundant operations?
常见陷阱
外企场景- error
Forgetting to handle character frequencies properly within the window.
- error
Inefficiently recalculating the hash table for each new substring.
- error
Failing to recognize the need for dynamic updates of the window.
进阶变体
外企场景- arrow_right_alt
Different constraints on the sizes of s1 and s2.
- arrow_right_alt
Handling strings with larger character sets (e.g., uppercase letters).
- arrow_right_alt
Modifying the problem to check for permutations in multiple substrings of s2.