LeetCode 438. 找到字符串中所有字母异位词：我的解题复盘与实践

在成功解决了“字母异位词分组”之后，我趁热打铁，继续挑战了相关的进阶题目——LeetCode 438. 找到字符串中所有字母异位词。

这篇博客主要记录我基于上一题核心思路的延伸，以及我的原始解法代码。

📝 题目描述

题目：给定两个字符串 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]

💡 我的解题思路：沿用“排序作为 Key”的核心思想

在做上一道题（字母异位词分组）时，我总结出了一个非常关键的规律：所有的字母异位词，如果在内部按字母顺序重新打散排序，最后得到的字符串一定是完全相同的。

既然如此，面对这道要在长字符串 s 中找目标字符串 p 的异位词的问题，我的直观思路如下：

1. 预处理目标串：先将目标字符串 p 转换为字符数组，进行字母排序。排序后重新组合成一个新的字符串 key，作为我们后续比对的“基准尺”。

2. 截取固定窗口：因为我们要找的是和 p 长度相等的子串，所以我们可以设置一个固定的步长（即 p.length()）。在长字符串 s 中，从头开始，每次截取这个固定长度的子串。

3. 逐一排序比对：将每次截取出来的子串也进行排序。如果排序后的子串与我们预先准备的 key 相等，就说明当前截取的子串是 p 的异位词。

4. 记录索引：把此时的起始索引 i 存入结果集合中即可。

💻 代码实现

以下是我根据上述思路编写的基础实现代码：

package com.okcl;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class FindAnagrams {
    public static void main(String[] args) {
        String s = "abab", p = "ab";
        int step = p.length();
        
        // 1. 预处理目标字符串 p，排序后形成比对的 key
        char[] pArray = p.toCharArray();
        Arrays.sort(pArray);
        String key = new String(pArray);
        
        // 使用 Set 存储结果索引，避免重复（虽然按此逻辑不会有重复）
        Set<Integer> set = new HashSet<>();
        
        // 2. 遍历长字符串 s，每次截取长度为 step 的子串
        for (int i = 0; i < s.length() - step + 1; i++) {
            String substring = s.substring(i, i + step);
            
            // 3. 对截取出来的子串进行排序
            char[] charArray = substring.toCharArray();
            Arrays.sort(charArray);
            String sortedSubstring = new String(charArray);
            
            // 4. 比对排序后的字符串是否一致
            if (sortedSubstring.equals(key)) {
                set.add(i);
            }
        }
        
        // 打印结果
        System.out.println(set);
    }
}

🔍 代码复盘与思考

这个解法的优势在于逻辑极其直白，非常符合直觉。一旦掌握了“排序做 Key”的技巧，顺理成章就能写出这套逻辑。

但这套代码在面对极大规模的数据时，暴露出了一些性能短板：

• 在每一次 for 循环中，我都执行了 substring（截取字符串）、toCharArray（转换为数组）、Arrays.sort（排序）和 new String（创建新对象）。

• 尤其当目标字符串 p 非常长时，频繁的 Arrays.sort 会产生极大的性能损耗。如果提交到 LeetCode 的大测试用例上，极有可能面临 超时 (Time Limit Exceeded) 的风险。

虽然这可能不是时间复杂度最优的解法，但它是理解“异位词核心特征”的基石。在实际的业务开发中，如果数据量不大且对性能没有极其苛刻的要求，这种代码的可读性其实是非常高的。

未来，我也会继续探索如何通过滑动窗口结合双数组计数的方式，来消除由于频繁排序带来的性能瓶颈，敬请期待后续的优化篇！