字符串的排列

字数 2383 2025-12-13 15:00:16

字符串的排列

题目描述
给你两个字符串 s1 和 s2，请判断 s2 是否包含 s1 的排列。换句话说，判断是否存在一个 s2 的子串，其包含 s1 中所有字符且不包含其他字符，且字符的出现次数与 s1 完全相同。

示例

输入：s1 = "ab", s2 = "eidbaooo"
输出：true（s2 的子串 "ba" 是 s1 的排列之一）
输入：s1 = "ab", s2 = "eidboaoo"
输出：false

解题思路
这个问题本质上是在 s2 中寻找一个长度等于 s1 长度的子串，其字符频率与 s1 完全相同。
我们可以用固定长度的滑动窗口在 s2 上移动，并借助哈希表来记录窗口中字符出现的频次，与 s1 的频次进行比较。

步骤分解

步骤 1：理解核心条件

排列意味着字符种类和每种字符的出现次数必须完全一致，但顺序可以任意。
如果 s1 长度大于 s2 长度，则一定不存在，直接返回 false。

步骤 2：数据结构选择

因为字符的范围可以是小写英文字母（本题通常限定为小写字母，但也可以扩展到 ASCII 字符），我们可以用长度 26 的数组作为哈希表，下标 0 到 25 分别对应 'a' 到 'z'。
数组的值表示该字符出现的次数。

步骤 3：建立 s1 的频率数组
例如 s1 = "ab"，则数组 countS1 为：
a 出现 1 次，b 出现 1 次，其余为 0。
具体表示：countS1[0] = 1, countS1[1] = 1，其余 0。

步骤 4：初始化滑动窗口的频率数组
设 s1 长度为 m。
我们先看 s2 的前 m 个字符，统计其字符频率到数组 countWindow 中。
比较 countS1 与 countWindow 是否完全相等。
如果相等，则找到了，返回 true。

步骤 5：滑动窗口

窗口每次向右移动 1 位：
- 移出窗口左边的字符（索引为 i - m 的字符），在 countWindow 中将其频率减 1。
- 移入窗口右边的字符（索引为 i 的字符），在 countWindow 中将其频率加 1。
每次移动后，比较 countS1 与 countWindow 是否相等。

步骤 6：比较两个数组相等的方法

如果每次窗口移动后都逐个比较 26 个位置，效率较低。
可以改为维护一个变量 matchCount，表示当前窗口频率与 s1 频率相同的字符有多少个。
初始时，先比较 s1 频率数组和 s2 前 m 个字符的频率数组，计算 matchCount。
每次窗口滑动时，只更新移出字符和移入字符对应的匹配情况，调整 matchCount。

详细执行过程（以 s1 = "ab", s2 = "eidbaooo" 为例）

m = 2, n = 8。
数组 countS1：a:1, b:1。
初始窗口 s2[0..1] = "ei"，频率数组 a:0, b:0, e:1, i:1。
- 与 countS1 比较，完全不匹配，matchCount 为 0（需要定义：当某个字符在窗口中的计数等于在 s1 中的计数时，这个字符匹配）。
窗口右移：
- 移除 s2[0] = 'e'，加入 s2[2] = 'd'，窗口 "id"，频率：i:1, d:1，仍然不匹配。
- 继续右移，直到窗口 "ba"：
  - 移除 s2[4] = 'o'，加入 s2[6] = 'a'？不对，我们一步步来。
    实际过程：
    初始 i=2: 窗口 s2[0..1]
    i=2: 新窗口 s2[1..2] = "id"
    i=3: 新窗口 s2[2..3] = "db"
    i=4: 新窗口 s2[3..4] = "bo"
    i=5: 新窗口 s2[4..5] = "oa"
    i=6: 新窗口 s2[5..6] = "ab" ← 这里频率 a:1, b:1，与 s1 频率完全相同，找到匹配，返回 true。

用 matchCount 优化的步骤

初始化数组 countS1[26] 记录 s1 的字符频率。
初始化数组 countWin[26] 记录当前窗口的字符频率。
先统计 s1 频率，同时统计 s2 前 m 个字符的频率。
初始化 matchCount = 0，对每个字符 c，如果 countWin[c] == countS1[c]，则 matchCount++。
滑动窗口，i 从 m 到 n-1：
- 移出字符 leftChar = s2[i-m]，移入字符 rightChar = s2[i]。
- 更新 countWin[leftChar]-- 前，先检查：
  - 如果更新前 countWin[leftChar] == countS1[leftChar]，则匹配数减少 1。
  - 更新后如果 countWin[leftChar] == countS1[leftChar]，则匹配数增加 1。
- 对 rightChar 同理更新。
- 如果更新后 matchCount == 26，说明所有字符频率匹配，返回 true。
循环结束返回 false。

复杂度分析

时间复杂度：O(n)，其中 n 是 s2 的长度，每个字符进出窗口各一次，每次更新常数时间。
空间复杂度：O(1)，只用了两个长度为 26 的数组。

核心思想
利用固定长度的滑动窗口和字符频率哈希表，可以在 O(n) 时间内判断 s2 中是否包含 s1 的排列。这种方法避免了枚举所有子串，是典型的“滑动窗口 + 哈希”经典题。

字符串的排列题目描述给你两个字符串 s1 和 s2 ，请判断 s2 是否包含 s1 的排列。换句话说，判断是否存在一个 s2 的子串，其包含 s1 中所有字符且不包含其他字符，且字符的出现次数与 s1 完全相同。示例输入：s1 = "ab", s2 = "eidbaooo" 输出：true（s2 的子串 "ba" 是 s1 的排列之一）输入：s1 = "ab", s2 = "eidboaoo" 输出：false 解题思路这个问题本质上是在 s2 中寻找一个长度等于 s1 长度的子串，其字符频率与 s1 完全相同。我们可以用固定长度的滑动窗口在 s2 上移动，并借助哈希表来记录窗口中字符出现的频次，与 s1 的频次进行比较。步骤分解步骤 1：理解核心条件排列意味着字符种类和每种字符的出现次数必须完全一致，但顺序可以任意。如果 s1 长度大于 s2 长度，则一定不存在，直接返回 false。步骤 2：数据结构选择因为字符的范围可以是小写英文字母（本题通常限定为小写字母，但也可以扩展到 ASCII 字符），我们可以用长度 26 的数组作为哈希表，下标 0 到 25 分别对应 'a' 到 'z' 。数组的值表示该字符出现的次数。步骤 3：建立 s1 的频率数组例如 s1 = "ab"，则数组 countS1 为： a 出现 1 次， b 出现 1 次，其余为 0。具体表示： countS1[0] = 1, countS1[1] = 1 ，其余 0。步骤 4：初始化滑动窗口的频率数组设 s1 长度为 m。我们先看 s2 的前 m 个字符，统计其字符频率到数组 countWindow 中。比较 countS1 与 countWindow 是否完全相等。如果相等，则找到了，返回 true。步骤 5：滑动窗口窗口每次向右移动 1 位：移出窗口左边的字符（索引为 i - m 的字符），在 countWindow 中将其频率减 1。移入窗口右边的字符（索引为 i 的字符），在 countWindow 中将其频率加 1。每次移动后，比较 countS1 与 countWindow 是否相等。步骤 6：比较两个数组相等的方法如果每次窗口移动后都逐个比较 26 个位置，效率较低。可以改为维护一个变量 matchCount ，表示当前窗口频率与 s1 频率相同的字符有多少个。初始时，先比较 s1 频率数组和 s2 前 m 个字符的频率数组，计算 matchCount 。每次窗口滑动时，只更新移出字符和移入字符对应的匹配情况，调整 matchCount 。详细执行过程（以 s1 = "ab", s2 = "eidbaooo" 为例） m = 2, n = 8。数组 countS1 ： a:1, b:1 。初始窗口 s2[ 0..1] = "ei"，频率数组 a:0, b:0, e:1, i:1 。与 countS1 比较，完全不匹配， matchCount 为 0（需要定义：当某个字符在窗口中的计数等于在 s1 中的计数时，这个字符匹配）。窗口右移：移除 s2[ 0] = 'e'，加入 s2[ 2] = 'd'，窗口 "id"，频率： i:1, d:1 ，仍然不匹配。继续右移，直到窗口 "ba"：移除 s2[ 4] = 'o'，加入 s2[ 6 ] = 'a'？不对，我们一步步来。实际过程：初始 i=2: 窗口 s2[ 0..1 ] i=2: 新窗口 s2[ 1..2 ] = "id" i=3: 新窗口 s2[ 2..3 ] = "db" i=4: 新窗口 s2[ 3..4 ] = "bo" i=5: 新窗口 s2[ 4..5 ] = "oa" i=6: 新窗口 s2[ 5..6 ] = "ab" ← 这里频率 a:1, b:1，与 s1 频率完全相同，找到匹配，返回 true。用 matchCount 优化的步骤初始化数组 countS1[26] 记录 s1 的字符频率。初始化数组 countWin[26] 记录当前窗口的字符频率。先统计 s1 频率，同时统计 s2 前 m 个字符的频率。初始化 matchCount = 0 ，对每个字符 c，如果 countWin[c] == countS1[c] ，则 matchCount++ 。滑动窗口，i 从 m 到 n-1：移出字符 leftChar = s2[i-m] ，移入字符 rightChar = s2[i] 。更新 countWin[leftChar]-- 前，先检查：如果更新前 countWin[leftChar] == countS1[leftChar] ，则匹配数减少 1。更新后如果 countWin[leftChar] == countS1[leftChar] ，则匹配数增加 1。对 rightChar 同理更新。如果更新后 matchCount == 26 ，说明所有字符频率匹配，返回 true。循环结束返回 false。复杂度分析时间复杂度：O(n)，其中 n 是 s2 的长度，每个字符进出窗口各一次，每次更新常数时间。空间复杂度：O(1)，只用了两个长度为 26 的数组。核心思想利用固定长度的滑动窗口和字符频率哈希表，可以在 O(n) 时间内判断 s2 中是否包含 s1 的排列。这种方法避免了枚举所有子串，是典型的“滑动窗口 + 哈希”经典题。