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

生活中的算法#

还记得小时候玩的”找朋友”游戏吗？每个人都有一个字母牌，需要找到拥有相同字母组合的伙伴。比如，拿着”ate”的同学要找到拿着”eat”或”tea”的同学。这其实就是在寻找字母异位词！

在实际应用中，字母异位词的检测有着广泛的用途。比如在密码学中检测可能的密文变体，或在文本分析中找出词语的不同排列组合。

问题描述#

题目目标#

给定两个字符串 s 和 p，请找出 s 中所有 p 的字母异位词子串，并返回这些子串的起始下标。答案顺序不限。

示例 1#

输入： s = "cbaebabacd", p = "abc" 输出： [0,6] 窗口示意：

索引 0: "cba" -> 是 "abc" 的异位词
索引 6: "bac" -> 是 "abc" 的异位词

text

说明： 只有从下标 0 和 6 开始的长度为 3 的窗口，字符组成与 p 完全一致。

补充说明#

异位词要求字符种类和每种字符的出现次数都相同。
题目返回的是所有合法窗口的起始位置，而不是这些子串本身。

最直观的解法：排序比较法#

最容易想到的方法是：取出s中长度等于p的每个子串，将子串和p分别排序后比较是否相等。如果相等，就找到了一个异位词。

让我们用一个例子来模拟这个过程：

s = "cbae", p = "abc"

检查所有长度为3的子串：
"cba" -> 排序后："abc" = "abc"（p排序后） ✓
"bae" -> 排序后："abe" ≠ "abc"（p排序后） ✗

plaintext

这种思路可以用Java代码这样实现：

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>(); // 存放所有满足条件的起始下标
    if (s.length() < p.length()) return result; // 边界情况：s 比 p 短，不可能存在异位词窗口

    char[] sortedP = p.toCharArray(); // 把 p 转为字符数组，便于排序比较
    Arrays.sort(sortedP); // 得到 p 的有序字符序列，后续窗口也排序后与它对比

    // 枚举 s 中每一个长度为 p.length() 的窗口起点 i
    for (int i = 0; i <= s.length() - p.length(); i++) {
        char[] window = s.substring(i, i + p.length()).toCharArray(); // 取出当前窗口并转成字符数组
        Arrays.sort(window); // 对当前窗口字符排序，便于与 sortedP 逐位比较

        // 若排序后完全相同，说明字符种类和频次都一致，即为异位词
        if (Arrays.equals(window, sortedP)) {
            result.add(i); // 记录这个异位词窗口的起始下标
        }
    }

    return result; // 返回所有起始位置
}

java

优化解法：滑动窗口 + 字符计数法#

仔细思考会发现，我们其实不需要对字符串排序。只要两个字符串包含相同的字符，且每个字符出现的次数相同，它们就是异位词。这启发我们使用字符计数的方法。

结合滑动窗口技巧，我们可以在一次遍历中完成所有比较。

算法原理#

使用数组记录p中每个字符的出现次数
维护一个大小等于p长度的滑动窗口
对窗口中的字符计数，与p的字符计数比较
当找到匹配时记录起始索引

算法步骤（伪代码）#

初始化两个大小为26的数组，分别记录p和窗口中字符出现次数
先统计p中字符出现次数
使用滑动窗口遍历s：
- 右边加入新字符，更新计数
- 当窗口大小超过p长度时，左边移除字符，更新计数
- 比较两个计数数组是否相等

示例运行#

让我们用s = “cbae”, p = “abc”模拟这个过程：

初始状态：
p的字符计数：[a:1, b:1, c:1]
窗口字符计数：[]

1. 添加'c'：
   窗口计数：[c:1]

2. 添加'b'：
   窗口计数：[b:1, c:1]

3. 添加'a'：
   窗口计数：[a:1, b:1, c:1]
   比较：相等 ✓
   记录索引0

4. 添加'e'，移除'c'：
   窗口计数：[a:1, b:1, e:1]
   比较：不等 ✗

plaintext

Java代码实现#

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>(); // 存放所有异位词窗口的起始下标
    if (s.length() < p.length()) return result; // 边界情况：s 长度不足以形成任何合法窗口

    int[] pCount = new int[26]; // 统计 p 中每个小写字母的出现次数
    int[] windowCount = new int[26]; // 统计当前滑动窗口中每个小写字母的出现次数

    // 先把目标串 p 的字符频次统计好，作为“匹配标准”
    for (char c : p.toCharArray()) {
        pCount[c - 'a']++; // c-'a' 把字符映射到 0~25 的数组下标
    }

    // 初始化第一个窗口 [0, p.length()-1] 的字符频次
    for (int i = 0; i < p.length(); i++) {
        windowCount[s.charAt(i) - 'a']++; // 把 s 前 p.length() 个字符计入窗口
    }

    // 先检查初始窗口是否已经是异位词
    if (Arrays.equals(pCount, windowCount)) {
        result.add(0); // 是的话，起点下标为 0
    }

    // 从第 p.length() 个字符开始右移窗口，每次右移 1 位
    for (int i = p.length(); i < s.length(); i++) {
        windowCount[s.charAt(i - p.length()) - 'a']--; // 移除离开窗口的最左字符
        windowCount[s.charAt(i) - 'a']++; // 加入新进入窗口的最右字符

        // 若当前窗口频次数组与 p 完全相等，则当前窗口是异位词
        if (Arrays.equals(pCount, windowCount)) {
            result.add(i - p.length() + 1); // 当前窗口的起点 = 终点 i - 窗口长度 + 1
        }
    }

    return result; // 返回所有匹配窗口起点
}

java

解法比较#

让我们比较这两种解法：

排序比较法：

时间复杂度：O(n·k·log k)，其中k是p的长度
空间复杂度：O(k)
优点：直观易懂
缺点：需要频繁排序，效率较低

滑动窗口 + 字符计数法：

时间复杂度：O(n)
空间复杂度：O(1)（因为数组大小固定为26）
优点：一次遍历就能得到结果，无需排序
缺点：需要额外空间存储字符计数

题目模式总结#

这道题体现了几个重要的算法思想：

滑动窗口：用于高效处理子串问题
计数统计：用计数替代排序来判断字符组成是否相同
空间换时间：使用额外空间来优化时间复杂度

这种解题模式在很多字符串问题中都有应用，比如：

无重复字符的最长子串
最小覆盖子串
字符串的排列

解决此类问题的通用思路是：

考虑能否用计数方法代替排序
思考是否可以用滑动窗口优化
注意窗口更新时的计数维护
考虑边界条件的处理

小结#

通过这道题，我们不仅学会了如何找到字符串中的所有异位词，更重要的是掌握了字符统计和滑动窗口相结合的技巧。从排序比较到字符计数，我们看到了如何通过巧妙的思路来提升算法效率。

记住，在处理字符串相关的问题时，排序并不总是最好的选择。有时候，简单的计数可能会带来意想不到的效率提升！