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

题目描述

给定两个字符串 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 仅包含小写字母

题目解析

题目在说什么

这道题想让我们在字符串 s 里面，找到所有和字符串 p 是“异位词”的子串，然后返回这些子串的起始位置（也就是子串第一个字符在 s 中的下标）。

“异位词”是什么意思呢？简单说，就是两个字符串包含的字母种类和每种字母的数量完全一样，只是字母的顺序可以不同。比如 "abc" 和 "cba" 就是异位词，因为都有 1 个 a、1 个 b、1 个 c。再比如 "ab" 和 "ba" 也是异位词。

题目给了两个例子：

• 例1：s = "cbaebabacd", p = "abc"。在 s 里，从下标 0 开始的子串 "cba" 是 "abc" 的异位词（字母相同，顺序不同），从下标 6 开始的子串 "bac" 也是。所以返回 [0, 6]。
• 例2：s = "abab", p = "ab"。从下标 0 开始的 "ab"、下标 1 开始的 "ba"、下标 2 开始的 "ab" 都是 "ab" 的异位词，所以返回 [0, 1, 2]。

注意：s 和 p 的长度最多有 3 万，而且只包含小写字母。这意味着我们需要一个高效的算法，不能暴力地去检查 s 里每一个可能的子串。

思路是怎么来的

想象一下，你有一个固定长度的“窗口”，这个窗口的长度刚好等于 p 的长度。你把这个窗口放在 s 的开头，看看窗口里的字母是不是和 p 是异位词。如果不是，你就把窗口向右滑动一个位置（也就是去掉最左边的一个字母，加入右边的一个新字母），然后再检查。这样一直滑到 s 的末尾，就能找到所有符合条件的子串。

这个“滑动窗口”的想法非常自然，就像我们用一把尺子在纸上量长度一样。关键是怎么快速判断“窗口里的字母”和“p 的字母”是不是异位词。

因为只有 26 个小写字母，我们可以用两个“计数器”来记录每个字母出现的次数。一个计数器记录 p 里每个字母出现了几次，另一个计数器记录当前窗口里每个字母出现了几次。每次窗口滑动时，我们只需要更新窗口计数器（去掉左边字母，加入右边字母），然后比较两个计数器是否完全相等。如果相等，就说明当前窗口是 p 的一个异位词，记录下窗口的起始位置。

这种方法比每次重新统计窗口里的字母要快得多，因为我们只做了很少的更新操作。

代码逐步拆解

我们来看参考代码，一步一步拆解。

第一步：定义需要的变量

List<Integer> res = new ArrayList<>();
int[] needs = new int[26];
for(char ch : p.toCharArray()){
    needs[ch - 'a']++;
}
int[] window = new int[26];

• res 用来存放所有符合条件的子串的起始下标。
• needs 是一个长度为 26 的数组，用来记录 p 中每个字母出现的次数。比如 needs[0] 对应字母 'a' 的次数，needs[1] 对应 'b'，以此类推。ch - 'a' 就是把字母转换成 0~25 的数字，比如 'a' 变成 0，'b' 变成 1。
• window 也是一个长度为 26 的数组，用来记录当前滑动窗口里每个字母出现的次数。

第二步：滑动窗口

int start = 0;
for(int end = 0; end < s.length(); end++){
    char cur = s.charAt(end);
    window[cur - 'a'] ++;
    // ... 后续操作
}

• start 是窗口的左边界，初始为 0。
• end 是窗口的右边界，我们从 0 开始，每次循环向右移动一位。
• 每次循环，我们把 s.charAt(end) 这个新字符加入窗口，并在 window 数组里把它对应的计数加 1。

第三步：检查当前窗口是否满足条件

if(isSame(window,needs)){
    res.add(start);
}

• 每次加入新字符后，我们调用 isSame 函数来比较 window 和 needs 是否完全一样。如果一样，说明当前窗口里的字母和 p 是异位词，就把窗口的起始位置 start 加入结果列表。
• isSame 函数很简单：遍历两个数组的每个位置，只要有一个位置的值不同，就返回 false；全部相同才返回 true。

第四步：控制窗口长度

if( end >= p.length() - 1 ){
    char chr = s.charAt(start);
    window[chr - 'a']--;
    start++;
}