438.找到字符串中所有字母异位词

LeetCode LeetCode 热题100 哈希表字符串滑动窗口

发布时间 : 2000-01-10 04:03

字数:4.9k 阅读 :

评论:

438.找到字符串中所有字母异位词

438.找到字符串中所有字母异位词

438.1 题目

给定两个字符串 s 和 p，找到 s 中所有 p 的字母异位词的子串，返回这些子串的起始索引。

不考虑答案输出的顺序。
字母异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1：

输入：s = "cbaebabacd", p = "abc"
输出：[0,6]
解释：
起始索引等于 0 的子串是 "cba"，它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac"，它是 "abc" 的异位词。

示例 2：

输入：s = "abab", p = "ab"
输出：[0,1,2]
解释：
起始索引等于 0 的子串是 "ab"，它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba"，它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab"，它是 "ab" 的异位词。

提示：

1 <= s.length, p.length <= 3 * 10^4
s 和 p 仅包含小写字母

438.2 题解

方法一：基础滑动窗口（直接比较计数数组）

思路

字母异位词的本质：26 个字母出现次数完全一致。固定窗口长度为 len(p)，在 s 上滑动窗口：用长度为 26 的数组记录当前窗口中每个字符的频次，再准备一个长度为 26 的数组记录 p 中每个字符的频次，每次窗口移动 1 步，更新窗口计数，并与 p 的计数数组比较。计数数组完全相同，则当前窗口是一个异位词，记录起始下标。

核心思想：滑动窗口 + 字符计数数组对比。

具体步骤：

统计 p 中每个字符的频次存入 targetCharCounts。
初始化窗口，统计 s 前 len(p) 个字符的频次存入 windowCharCounts。
比较两个数组，相同则记录起始索引 0。
滑动窗口：每次移除左边字符，添加右边字符，比较计数数组。

举例：对于 s = "cbaebabacd", p = "abc"：

窗口长度 3，targetCharCounts = [1,1,1,0,...]（a,b,c 各 1 个）
窗口 "cba"：计数 [1,1,1,0,...]，匹配，记录索引 0
窗口 "bae"：计数 [1,1,0,0,...,e:1]，不匹配
…
窗口 "bac"：计数 [1,1,1,0,...]，匹配，记录索引 6
结果：[0, 6]

复杂度分析

时间复杂度：O(n + m)，本质上是 O(n * 26)，26 为常数。
空间复杂度：O(1)，两个固定长度为 26 的数组。

代码

/// <summary>
/// 方法一：基础滑动窗口法（字符计数数组对比）
/// 核心逻辑：用等长窗口滑动，通过对比窗口与目标字符串的字符计数数组，判断是否为异位词
/// 时间复杂度：O(n + m)，n=s长度，m=p长度（实际为O(n + m + 26*(n-m))，26为常数可忽略）
/// 空间复杂度：O(1)（固定26长度的数组，属于常数级空间）
/// </summary>
/// <param name="s">源字符串</param>
/// <param name="p">目标字符串（异位词匹配基准）</param>
/// <returns>所有异位词在sourceStr中的起始索引列表</returns>
public static IList<int> FindAnagrams1(string s, string p)
{
    int sourceLength = s.Length;
    int targetLength = p.Length;

    // 边界校验：源字符串比目标短，无匹配可能
    if (sourceLength < targetLength)
    {
        return new List<int>();
    }

    // 存储所有异位词的起始索引
    IList<int> resultList = new List<int>();

    // 滑动窗口内字符的计数数组（索引0-25对应a-z）
    int[] windowCharCounts = new int[26];

    // 目标字符串的字符计数数组（基准值）
    int[] targetCharCounts = new int[26];

    // 初始化：统计第一个窗口和目标字符串的字符频率
    for (int i = 0; i < targetLength; ++i)
    {
        windowCharCounts[s[i] - 'a']++;
        targetCharCounts[p[i] - 'a']++;
    }

    // 校验第一个窗口是否为异位词,就是判断两个频率数组是否一致
    if (Enumerable.SequenceEqual(windowCharCounts, targetCharCounts))
    {
        resultList.Add(0);
    }

    // 滑动窗口：逐位移动，更新计数并校验
    for (int i = 0; i < sourceLength - targetLength; ++i)
    {
        // 移除窗口左边界字符（计数-1）
        windowCharCounts[s[i] - 'a']--;
        // 添加窗口右边界新字符（计数+1）
        windowCharCounts[s[i + targetLength] - 'a']++;

        // 校验当前窗口是否匹配目标字符频率,就是判断两个频率数组是否一致
        if (Enumerable.SequenceEqual(windowCharCounts, targetCharCounts))
        {
            resultList.Add(i + 1);
        }
    }

    return resultList;
}

方法二：差值数组 + 差异数优化滑动窗口

定义 diff[c] = 窗口中字符 c 的数量 - p 中字符 c 的数量，维护一个整数 differentCharCount 记录有多少个字符 diff[c] != 0。如果 differentCharCount == 0，说明当前窗口是异位词。每次窗口右移只需更新两个字符的差值，避免全数组比较。

复杂度分析：

时间复杂度：O(n + m)，常数更小。
空间复杂度：O(1)，固定长度 26 的数组。

/// <summary>
/// 查找源字符串中目标字符串所有异位词的起始索引（优化滑动窗口法）
/// 核心思路：通过「字符计数差值数组」+「差异数」替代全数组对比，降低时间复杂度
/// 时间复杂度：O(n + m)（n=源字符串长度，m=目标字符串长度，26个字母为常数级）
/// 空间复杂度：O(1)（仅使用固定长度26的数组，无额外扩容开销）
/// </summary>
/// <param name="s">源字符串（待查找的主字符串）</param>
/// <param name="p">目标字符串（异位词匹配基准）</param>
/// <returns>所有异位词在s中的起始索引列表</returns>
public static IList<int> FindAnagrams2(string s, string p)
{
    // 1. 核心变量定义（每个变量均标注语义+设计目的）
    // 源字符串总长度：用于后续滑动窗口的边界控制
    int sourceLength = s.Length;
    // 目标字符串总长度：滑动窗口的固定尺寸（异位词长度必须与p一致）
    int targetLength = p.Length;

    // 边界校验：源字符串比目标短，无法构造等长窗口，直接返回空列表
    if (sourceLength < targetLength)
    {
        return new List<int>();
    }

    // 结果容器：存储所有符合条件的异位词起始索引（用IList保证接口通用性）
    IList<int> resultList = new List<int>();

    // 字符计数差值数组：核心优化点，公式=窗口内字符数 - 目标字符串字符数
    // 索引0-25对应a-z，值为0表示该字符在窗口和目标中数量相等；非0表示不匹配
    int[] charCountDifference = new int[26];

    // 2. 初始化第一个窗口的差值数组（窗口范围：s[0]~s[targetLength-1]）
    // 遍历目标长度次，同时统计窗口和目标的字符差值
    for (int i = 0; i < targetLength; ++i)
    {
        // 窗口内字符计数+1：等价于 窗口数-目标数 中的「窗口数增加」
        charCountDifference[s[i] - 'a']++;
        // 目标字符计数-1：等价于 窗口数-目标数 中的「目标数增加（差值减少）」
        // 两步合并最终实现：charCountDifference = 窗口数 - 目标数
        charCountDifference[p[i] - 'a']--;
    }

    // 3. 统计初始差异数（差值数组中非0的字符种类数）
    // 差异数=0 → 所有字符的窗口数=目标数 → 第一个窗口是异位词
    int differentCharCount = 0;
    for (int i = 0; i < 26; ++i)
    {
        // 仅统计不匹配的字符种类（非0即不匹配）
        if (charCountDifference[i] != 0)
        {
            differentCharCount++;
        }
    }

    // 4. 校验第一个窗口是否为异位词
    // 差异数为0表示所有字符的窗口数与目标数完全一致
    if (differentCharCount == 0)
    {
        resultList.Add(0); // 第一个窗口起始索引为0
    }

    // 5. 滑动窗口核心逻辑（逐位右移，仅更新变化的字符，避免全数组对比）
    // 循环次数=源长度-目标长度：保证窗口始终能容纳目标长度的字符
    for (int i = 0; i < sourceLength - targetLength; ++i)
    {
        // ---------------- 处理左边界：移除滑出窗口的字符 ----------------
        // 滑出的字符（当前窗口最左侧字符）
        char leftChar = s[i];
        // 字符对应的数组索引（a-z映射到0-25）
        int leftCharIndex = leftChar - 'a';

        // 预判移除字符对差异数的影响（仅处理会改变匹配状态的情况）
        // 情况1：移除前差值=1 → 窗口数=目标数+1（仅窗口多1个）
        // 移除后差值=0 → 该字符从「不匹配」变「匹配」→ 差异数减1
        if (charCountDifference[leftCharIndex] == 1)
        {
            differentCharCount--;
        }
        // 情况2：移除前差值=0 → 窗口数=目标数（刚好匹配）
        // 移除后差值=-1 → 该字符从「匹配」变「不匹配」→ 差异数加1
        else if (charCountDifference[leftCharIndex] == 0)
        {
            differentCharCount++;
        }
        // 其他情况（如差值=2/-1）：移除后仍不匹配，差异数无变化，无需处理

        // 实际更新差值数组：移除左边界字符（窗口数-1 → 差值-1）
        // 必须先预判影响再修改数组，否则预判的差值是修改后的值，会计算错误
        charCountDifference[leftCharIndex]--;

        // ---------------- 处理右边界：添加滑入窗口的新字符 ----------------
        // 滑入的字符（窗口右移后新增的右侧字符）
        char rightChar = s[i + targetLength];
        // 字符对应的数组索引
        int rightCharIndex = rightChar - 'a';

        // 预判添加字符对差异数的影响（仅处理会改变匹配状态的情况）
        // 情况1：添加前差值=-1 → 窗口数=目标数-1（仅目标多1个）
        // 添加后差值=0 → 该字符从「不匹配」变「匹配」→ 差异数减1
        if (charCountDifference[rightCharIndex] == -1)
        {
            differentCharCount--;
        }
        // 情况2：添加前差值=0 → 窗口数=目标数（刚好匹配）
        // 添加后差值=1 → 该字符从「匹配」变「不匹配」→ 差异数加1
        else if (charCountDifference[rightCharIndex] == 0)
        {
            differentCharCount++;
        }
        // 其他情况（如差值=2/-2）：添加后仍不匹配，差异数无变化，无需处理

        // 实际更新差值数组：添加右边界字符（窗口数+1 → 差值+1）
        // 同理：先预判影响再修改数组，保证预判依据是修改前的原始值
        charCountDifference[rightCharIndex]++;

        // 6. 校验当前窗口是否为异位词
        // 差异数=0 → 所有字符的窗口数=目标数 → 是异位词
        // 新窗口起始索引=i+1：因为当前循环i是「上一个窗口的左边界」，右移后起始索引+1
        if (differentCharCount == 0)
        {
            resultList.Add(i + 1);
        }
    }

    // 返回所有符合条件的起始索引
    return resultList;
}

438.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定两个字符串 s 和 p，找到 s 中所有 p 的字母异位词的子串，返回这些子串的起始索引。
        // 不考虑答案输出的顺序。
        // 字母异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

        // 示例 1:
        // 输入: s = "cbaebabacd", p = "abc"
        // 输出: [0,6]
        // 解释:
        // 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
        // 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

        // 示例 2:
        // 输入: s = "abab", p = "ab"
        // 输出: [0,1,2]
        // 解释:
        // 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
        // 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
        // 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

        // 提示:
        // 1 <= s.length, p.length <= 3 * 104
        // s 和 p 仅包含小写字母

        #endregion

        #region 测试

        // 示例 1
        string s1 = "cbaebabacd";
        string p1 = "abc";
        IList<int> result11 = FindAnagrams1(s1, p1);
        IList<int> result12 = FindAnagrams2(s1, p1);
        Console.WriteLine($"示例1 方法1 输出：[{string.Join(",", result11)}]");
        Console.WriteLine($"示例1 方法2 输出：[{string.Join(",", result12)}]");

        // 示例 2
        string s2 = "abab";
        string p2 = "ab";
        IList<int> result21 = FindAnagrams1(s2, p2);
        IList<int> result22 = FindAnagrams2(s2, p2);
        Console.WriteLine($"示例2 方法1 输出：[{string.Join(",", result21)}]");
        Console.WriteLine($"示例2 方法2 输出：[{string.Join(",", result22)}]");

        #endregion
    }

    #region 答案

    /// <summary>
    /// 方法一：基础滑动窗口法（字符计数数组对比）
    /// 核心逻辑：用等长窗口滑动，通过对比窗口与目标字符串的字符计数数组，判断是否为异位词
    /// 时间复杂度：O(n + m)，n=s长度，m=p长度（实际为O(n + m + 26*(n-m))，26为常数可忽略）
    /// 空间复杂度：O(1)（固定26长度的数组，属于常数级空间）
    /// </summary>
    /// <param name="s">源字符串</param>
    /// <param name="p">目标字符串（异位词匹配基准）</param>
    /// <returns>所有异位词在sourceStr中的起始索引列表</returns>
    public static IList<int> FindAnagrams1(string s, string p)
    {
        int sourceLength = s.Length;
        int targetLength = p.Length;

        // 边界校验：源字符串比目标短，无匹配可能
        if (sourceLength < targetLength)
        {
            return new List<int>();
        }

        // 存储所有异位词的起始索引
        IList<int> resultList = new List<int>();

        // 滑动窗口内字符的计数数组（索引0-25对应a-z）
        int[] windowCharCounts = new int[26];

        // 目标字符串的字符计数数组（基准值）
        int[] targetCharCounts = new int[26];

        // 初始化：统计第一个窗口和目标字符串的字符频率
        for (int i = 0; i < targetLength; ++i)
        {
            windowCharCounts[s[i] - 'a']++;
            targetCharCounts[p[i] - 'a']++;
        }

        // 校验第一个窗口是否为异位词,就是判断两个频率数组是否一致
        if (Enumerable.SequenceEqual(windowCharCounts, targetCharCounts))
        {
            resultList.Add(0);
        }

        // 滑动窗口：逐位移动，更新计数并校验
        for (int i = 0; i < sourceLength - targetLength; ++i)
        {
            // 移除窗口左边界字符（计数-1）
            windowCharCounts[s[i] - 'a']--;
            // 添加窗口右边界新字符（计数+1）
            windowCharCounts[s[i + targetLength] - 'a']++;

            // 校验当前窗口是否匹配目标字符频率,就是判断两个频率数组是否一致
            if (Enumerable.SequenceEqual(windowCharCounts, targetCharCounts))
            {
                resultList.Add(i + 1);
            }
        }

        return resultList;
    }

    /// <summary>
    /// 查找源字符串中目标字符串所有异位词的起始索引（优化滑动窗口法）
    /// 核心思路：通过「字符计数差值数组」+「差异数」替代全数组对比，降低时间复杂度
    /// 时间复杂度：O(n + m)（n=源字符串长度，m=目标字符串长度，26个字母为常数级）
    /// 空间复杂度：O(1)（仅使用固定长度26的数组，无额外扩容开销）
    /// </summary>
    /// <param name="s">源字符串（待查找的主字符串）</param>
    /// <param name="p">目标字符串（异位词匹配基准）</param>
    /// <returns>所有异位词在s中的起始索引列表</returns>
    public static IList<int> FindAnagrams2(string s, string p)
    {
        // 1. 核心变量定义（每个变量均标注语义+设计目的）
        // 源字符串总长度：用于后续滑动窗口的边界控制
        int sourceLength = s.Length;
        // 目标字符串总长度：滑动窗口的固定尺寸（异位词长度必须与p一致）
        int targetLength = p.Length;

        // 边界校验：源字符串比目标短，无法构造等长窗口，直接返回空列表
        if (sourceLength < targetLength)
        {
            return new List<int>();
        }

        // 结果容器：存储所有符合条件的异位词起始索引（用IList保证接口通用性）
        IList<int> resultList = new List<int>();

        // 字符计数差值数组：核心优化点，公式=窗口内字符数 - 目标字符串字符数
        // 索引0-25对应a-z，值为0表示该字符在窗口和目标中数量相等；非0表示不匹配
        int[] charCountDifference = new int[26];

        // 2. 初始化第一个窗口的差值数组（窗口范围：s[0]~s[targetLength-1]）
        // 遍历目标长度次，同时统计窗口和目标的字符差值
        for (int i = 0; i < targetLength; ++i)
        {
            // 窗口内字符计数+1：等价于 窗口数-目标数 中的「窗口数增加」
            charCountDifference[s[i] - 'a']++;
            // 目标字符计数-1：等价于 窗口数-目标数 中的「目标数增加（差值减少）」
            // 两步合并最终实现：charCountDifference = 窗口数 - 目标数
            charCountDifference[p[i] - 'a']--;
        }

        // 3. 统计初始差异数（差值数组中非0的字符种类数）
        // 差异数=0 → 所有字符的窗口数=目标数 → 第一个窗口是异位词
        int differentCharCount = 0;
        for (int i = 0; i < 26; ++i)
        {
            // 仅统计不匹配的字符种类（非0即不匹配）
            if (charCountDifference[i] != 0)
            {
                differentCharCount++;
            }
        }

        // 4. 校验第一个窗口是否为异位词
        // 差异数为0表示所有字符的窗口数与目标数完全一致
        if (differentCharCount == 0)
        {
            resultList.Add(0); // 第一个窗口起始索引为0
        }

        // 5. 滑动窗口核心逻辑（逐位右移，仅更新变化的字符，避免全数组对比）
        // 循环次数=源长度-目标长度：保证窗口始终能容纳目标长度的字符
        for (int i = 0; i < sourceLength - targetLength; ++i)
        {
            // ---------------- 处理左边界：移除滑出窗口的字符 ----------------
            // 滑出的字符（当前窗口最左侧字符）
            char leftChar = s[i];
            // 字符对应的数组索引（a-z映射到0-25）
            int leftCharIndex = leftChar - 'a';

            // 预判移除字符对差异数的影响（仅处理会改变匹配状态的情况）
            // 情况1：移除前差值=1 → 窗口数=目标数+1（仅窗口多1个）
            // 移除后差值=0 → 该字符从「不匹配」变「匹配」→ 差异数减1
            if (charCountDifference[leftCharIndex] == 1)
            {
                differentCharCount--;
            }
            // 情况2：移除前差值=0 → 窗口数=目标数（刚好匹配）
            // 移除后差值=-1 → 该字符从「匹配」变「不匹配」→ 差异数加1
            else if (charCountDifference[leftCharIndex] == 0)
            {
                differentCharCount++;
            }
            // 其他情况（如差值=2/-1）：移除后仍不匹配，差异数无变化，无需处理

            // 实际更新差值数组：移除左边界字符（窗口数-1 → 差值-1）
            // 必须先预判影响再修改数组，否则预判的差值是修改后的值，会计算错误
            charCountDifference[leftCharIndex]--;

            // ---------------- 处理右边界：添加滑入窗口的新字符 ----------------
            // 滑入的字符（窗口右移后新增的右侧字符）
            char rightChar = s[i + targetLength];
            // 字符对应的数组索引
            int rightCharIndex = rightChar - 'a';

            // 预判添加字符对差异数的影响（仅处理会改变匹配状态的情况）
            // 情况1：添加前差值=-1 → 窗口数=目标数-1（仅目标多1个）
            // 添加后差值=0 → 该字符从「不匹配」变「匹配」→ 差异数减1
            if (charCountDifference[rightCharIndex] == -1)
            {
                differentCharCount--;
            }
            // 情况2：添加前差值=0 → 窗口数=目标数（刚好匹配）
            // 添加后差值=1 → 该字符从「匹配」变「不匹配」→ 差异数加1
            else if (charCountDifference[rightCharIndex] == 0)
            {
                differentCharCount++;
            }
            // 其他情况（如差值=2/-2）：添加后仍不匹配，差异数无变化，无需处理

            // 实际更新差值数组：添加右边界字符（窗口数+1 → 差值+1）
            // 同理：先预判影响再修改数组，保证预判依据是修改前的原始值
            charCountDifference[rightCharIndex]++;

            // 6. 校验当前窗口是否为异位词
            // 差异数=0 → 所有字符的窗口数=目标数 → 是异位词
            // 新窗口起始索引=i+1：因为当前循环i是「上一个窗口的左边界」，右移后起始索引+1
            if (differentCharCount == 0)
            {
                resultList.Add(i + 1);
            }
        }

        // 返回所有符合条件的起始索引
        return resultList;
    }

    #endregion
}

438.4 运行结果

示例1 方法1 输出：[0,6]
示例1 方法2 输出：[0,6]
示例2 方法1 输出：[0,1,2]
示例2 方法2 输出：[0,1,2]

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com