寻找字符串中所有变位词
字数 2706 2025-12-10 21:05:33

寻找字符串中所有变位词

题目描述
给定一个字符串 s 和一个非空字符串 p，在 s 中找到 p 的所有变位词（字母异位词）的起始索引。变位词指字母相同但排列不同的字符串，例如 "abc" 的变位词包括 "acb"、"bac" 等。返回这些起始索引，顺序不限。
示例：
输入：s = "cbaebabacd", p = "abc"
输出：[0, 6]
解释：

  • 索引 0 开始的子串 "cba" 是 "abc" 的变位词。
  • 索引 6 开始的子串 "bac" 是 "abc" 的变位词。

解题过程详解
本题的核心是在长字符串 s 中高效匹配短字符串 p 的变位词。关键在于判断一个子串是否与 p 的字符组成完全相同（即字符频次一致）。哈希表（或数组模拟哈希表）是记录字符频次的理想工具。我们将通过“滑动窗口 + 字符频次哈希”来解决。

步骤1：理解问题本质

  1. 变位词的定义是字符种类相同、各字符出现次数也相同，与字符顺序无关。
  2. 因此，若 s 中某个子串的字符频次分布与 p 完全相同，则该子串是 p 的变位词。
  3. 需要在 s 中找出所有满足条件的子串的起始索引。

步骤2：选择数据结构记录字符频次

  • 字符范围：假设字符串仅包含小写英文字母（实际可扩展至 ASCII 或 Unicode，但核心逻辑不变）。
  • 用一个长度为 26 的整数数组 countP 表示 p 的字符频次。例如，p = "abc" 时：
    countP[0] = 1（'a' 出现1次）
    countP[1] = 1（'b' 出现1次）
    countP[2] = 1（'c' 出现1次）
    其余为 0。
  • 同理，用一个长度相同的数组 countWindow 记录当前 s 中考察的子串的字符频次。

步骤3：滑动窗口的基本思路

  1. 窗口长度固定为 len(p)，因为变位词必须与 p 等长。
  2. 从 s 的起始位置开始，依次向右滑动窗口，每次移动一个字符。
  3. 在每一步中，比较 countWindow 与 countP 是否完全一致。若一致，则当前窗口起始索引符合条件。
  4. 直接每次重新统计窗口频次并比较，时间复杂度为 O(26 × n)，可行但稍显低效。下面我们优化为 O(n)。

步骤4：优化——增量更新窗口频次

  • 初始时，先统计 p 的频次 countP，并统计 s 中第一个窗口（前 len(p) 个字符）的频次 countWindow。
  • 之后滑动窗口时，只需：
    a. 将离开窗口的字符频次减 1。
    b. 将进入窗口的字符频次加 1。
  • 这样无需每次重新统计整个窗口，更新频次的时间为 O(1)。

步骤5：高效比较频次数组
比较两个长度 26 的数组是否相等，在每次滑动后都做一次完整比较，代价是 O(26) 即 O(1)。但我们可以进一步优化：

  • 用一个变量 matchCount 记录当前窗口与 p 中频次相等的字符个数。
  • 初始时，比较 countP 与第一个窗口的 countWindow，统计相等的字符数，存入 matchCount。
  • 每次窗口滑动时，只更新受影响的字符的匹配状态，并调整 matchCount。
  • 若 matchCount == 26，说明当前窗口频次与 p 完全一致。

步骤6：具体更新规则
设窗口右移一步：

  1. 移出字符 leftChar = s[start]（start 为旧窗口起始索引）。
    • 更新前，若 countWindow[leftChar] == countP[leftChar]，说明移出前该字符频次相等，移出后不再相等，因此 matchCount -= 1。
    • 移出操作：countWindow[leftChar] -= 1。
    • 移出后，若 countWindow[leftChar] == countP[leftChar]，说明移出后该字符频次又变得相等，因此 matchCount += 1。
  2. 移入字符 rightChar = s[end]（end 为新窗口结束索引）。
    • 更新前，若 countWindow[rightChar] == countP[rightChar]，同理移入前相等，移入后可能不等，matchCount -= 1。
    • 移入操作：countWindow[rightChar] += 1。
    • 移入后，若 countWindow[rightChar] == countP[rightChar]，说明移入后变得相等，matchCount += 1。
  3. 每次更新后，若 matchCount == 26，则新窗口起始索引（start + 1）符合条件，加入结果列表。

步骤7：算法步骤拆解
以 s = "cbaebabacd", p = "abc" 为例：

  1. 初始化：
    • countP = {a:1, b:1, c:1}，其余 0。
    • 第一个窗口 s[0:3] = "cba" 的 countWindow = {a:1, b:1, c:1}。
    • 比较得 matchCount = 26（所有字符频次相等），索引 0 加入结果。
  2. 窗口右移一位，新窗口 s[1:4] = "b a e"：
    • 移出 s[0] = 'c'，移入 s[3] = 'e'。
    • 更新后 countWindow = {a:1, b:1, c:0, e:1}，与 countP 不等，matchCount 非 26。
  3. 继续滑动，直到窗口 s[6:9] = "b a c"：
    • 此时 countWindow = {a:1, b:1, c:1}，matchCount == 26，索引 6 加入结果。
  4. 最终结果 [0, 6]。

步骤8：边界与扩展

  • 若 len(s) < len(p)，直接返回空列表。
  • 若字符范围扩大（如包含大写、Unicode），可用 HashMap<Character, Integer> 代替数组，但比较复杂度稍高。
  • 此法时间复杂度 O(n)，空间复杂度 O(1)（数组大小固定）。

关键点总结

  1. 变位词判定转化为字符频次相等问题。
  2. 固定长度滑动窗口，增量更新频次数组。
  3. 用 matchCount 跟踪匹配字符数，避免每次全数组比较。
  4. 此方法高效且易于实现，是哈希表结合滑动窗口的经典应用。
寻找字符串中所有变位词 题目描述 给定一个字符串 s 和一个非空字符串 p ，在 s 中找到 p 的所有 变位词 （字母异位词）的起始索引。变位词指字母相同但排列不同的字符串，例如 "abc" 的变位词包括 "acb" 、 "bac" 等。返回这些起始索引，顺序不限。 示例： 输入： s = "cbaebabacd" , p = "abc" 输出： [0, 6] 解释： 索引 0 开始的子串 "cba" 是 "abc" 的变位词。 索引 6 开始的子串 "bac" 是 "abc" 的变位词。 解题过程详解 本题的核心是 在长字符串 s 中高效匹配短字符串 p 的变位词 。关键在于判断一个子串是否与 p 的字符组成完全相同（即字符频次一致）。哈希表（或数组模拟哈希表）是记录字符频次的理想工具。我们将通过“滑动窗口 + 字符频次哈希”来解决。 步骤1：理解问题本质 变位词的定义是 字符种类相同、各字符出现次数也相同 ，与字符顺序无关。 因此，若 s 中某个子串的字符频次分布与 p 完全相同，则该子串是 p 的变位词。 需要在 s 中找出所有满足条件的子串的起始索引。 步骤2：选择数据结构记录字符频次 字符范围：假设字符串仅包含小写英文字母（实际可扩展至 ASCII 或 Unicode，但核心逻辑不变）。 用一个长度为 26 的整数数组 countP 表示 p 的字符频次。例如， p = "abc" 时： countP[0] = 1 （ 'a' 出现1次） countP[1] = 1 （ 'b' 出现1次） countP[2] = 1 （ 'c' 出现1次） 其余为 0。 同理，用一个长度相同的数组 countWindow 记录当前 s 中考察的子串的字符频次。 步骤3：滑动窗口的基本思路 窗口长度固定为 len(p) ，因为变位词必须与 p 等长。 从 s 的起始位置开始，依次向右滑动窗口，每次移动一个字符。 在每一步中，比较 countWindow 与 countP 是否完全一致。若一致，则当前窗口起始索引符合条件。 直接每次重新统计窗口频次并比较，时间复杂度为 O(26 × n)，可行但稍显低效。下面我们优化为 O(n)。 步骤4：优化——增量更新窗口频次 初始时，先统计 p 的频次 countP ，并统计 s 中 第一个窗口 （前 len(p) 个字符）的频次 countWindow 。 之后滑动窗口时，只需： a. 将 离开窗口 的字符频次减 1。 b. 将 进入窗口 的字符频次加 1。 这样无需每次重新统计整个窗口，更新频次的时间为 O(1)。 步骤5：高效比较频次数组 比较两个长度 26 的数组是否相等，在每次滑动后都做一次完整比较，代价是 O(26) 即 O(1)。但我们可以进一步优化： 用一个变量 matchCount 记录当前窗口与 p 中 频次相等的字符个数 。 初始时，比较 countP 与第一个窗口的 countWindow ，统计相等的字符数，存入 matchCount 。 每次窗口滑动时，只更新受影响的字符的匹配状态，并调整 matchCount 。 若 matchCount == 26 ，说明当前窗口频次与 p 完全一致。 步骤6：具体更新规则 设窗口右移一步： 移出字符 leftChar = s[start] （ start 为旧窗口起始索引）。 更新前，若 countWindow[leftChar] == countP[leftChar] ，说明移出前该字符频次相等，移出后不再相等，因此 matchCount -= 1 。 移出操作： countWindow[leftChar] -= 1 。 移出后，若 countWindow[leftChar] == countP[leftChar] ，说明移出后该字符频次又变得相等，因此 matchCount += 1 。 移入字符 rightChar = s[end] （ end 为新窗口结束索引）。 更新前，若 countWindow[rightChar] == countP[rightChar] ，同理移入前相等，移入后可能不等， matchCount -= 1 。 移入操作： countWindow[rightChar] += 1 。 移入后，若 countWindow[rightChar] == countP[rightChar] ，说明移入后变得相等， matchCount += 1 。 每次更新后，若 matchCount == 26 ，则新窗口起始索引（ start + 1 ）符合条件，加入结果列表。 步骤7：算法步骤拆解 以 s = "cbaebabacd" , p = "abc" 为例： 初始化： countP = {a:1, b:1, c:1} ，其余 0。 第一个窗口 s[0:3] = "cba" 的 countWindow = {a:1, b:1, c:1} 。 比较得 matchCount = 26 （所有字符频次相等），索引 0 加入结果。 窗口右移一位，新窗口 s[1:4] = "b a e" ： 移出 s[0] = 'c' ，移入 s[3] = 'e' 。 更新后 countWindow = {a:1, b:1, c:0, e:1} ，与 countP 不等， matchCount 非 26。 继续滑动，直到窗口 s[6:9] = "b a c" ： 此时 countWindow = {a:1, b:1, c:1} ， matchCount == 26 ，索引 6 加入结果。 最终结果 [0, 6] 。 步骤8：边界与扩展 若 len(s) < len(p) ，直接返回空列表。 若字符范围扩大（如包含大写、Unicode），可用 HashMap<Character, Integer> 代替数组，但比较复杂度稍高。 此法时间复杂度 O(n)，空间复杂度 O(1)（数组大小固定）。 关键点总结 变位词判定转化为 字符频次相等 问题。 固定长度滑动窗口，增量更新频次数组。 用 matchCount 跟踪匹配字符数，避免每次全数组比较。 此方法高效且易于实现，是哈希表结合滑动窗口的经典应用。