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

力扣题目链接 (opens new window)

题目描述

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

思路

暴力解法

一个字符串要成为 p 的字母异位词，长度一定要和 p 相同。

最直观的想法是：枚举 s 中所有长度为 p.length() 的子串，将每个子串排序后再和排好序的 p 比较。

假设 s 的长度为 n，p 的长度为 m，这种做法的时间复杂度是 O((n - m + 1) × m log m)。相邻两个子串明明只差一个字符，却每次都要重新排序，做了很多重复工作。

如果相邻区间之间只有“移出一个字符、移入一个字符”的差别，就应该想到滑动窗口。

定长滑动窗口

为什么这里是定长窗口？

因为字母异位词只是字符排列顺序不同，字符数量不会改变，所以候选子串的长度必须等于 p 的长度 m。窗口大了或小了，都不可能成为 p 的字母异位词。

我们用两个长度为 26 的数组：

• need：统计 p 中每个字母出现的次数
• window：统计当前窗口中每个字母出现的次数

当两个频次数组完全相同时，说明当前窗口和 p 包含的字符及数量都相同，当前窗口就是一个字母异位词。

窗口每次向右移动一格，只需要做两件事：

1. 将新进入窗口的字符计数加一
2. 将离开窗口的字符计数减一

窗口不需要重新排序，也不需要重新统计，这就是滑动窗口省时间的地方。

这里题目明确说明只有小写字母，所以用长度为 26 的数组比哈希表更直接。比较两个数组虽然要检查 26 个位置，但 26 是固定常数，因此整体仍然是线性时间复杂度。

完整流程如下：

1. 统计 p 的字符频次
2. 右指针逐个将 s 中的字符加入窗口
3. 当窗口长度超过 m 时，移出窗口最左侧的字符
4. 当窗口长度等于 m 时，比较 window 和 need
5. 如果二者相同，将窗口左端点 right - m + 1 加入结果

模拟过程

以 s = "cbaebabacd"，p = "abc" 为例。

p 的长度为 3，所以窗口大小始终保持为 3。p 的字符频次为 a:1、b:1、c:1。

窗口的完整移动过程如下：

窗口范围	子串	本次变化	是否匹配	结果
[0, 2]	cba	初始化窗口	是	[0]
[1, 3]	bae	移出 c，移入 e	否	[0]
[2, 4]	aeb	移出 b，移入 b	否	[0]
[3, 5]	eba	移出 a，移入 a	否	[0]
[4, 6]	bab	移出 e，移入 b	否	[0]
[5, 7]	aba	移出 b，移入 a	否	[0]
[6, 8]	bac	移出 a，移入 c	是	[0, 6]
[7, 9]	acd	移出 b，移入 d	否	[0, 6]

很多录友容易把这道题写成可变窗口，但其实这里没有“满足条件后继续收缩”的过程。窗口一旦达到 m，之后每加入一个字符，就必须同时移出一个字符，窗口长度始终不变。

解题代码

C++

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = s.size();
        int m = p.size();
        vector<int> result;

        if (m > n) return result;

        vector<int> need(26, 0);
        vector<int> window(26, 0);
        for (char c : p) need[c - 'a']++;

        for (int right = 0; right < n; right++) {
            window[s[right] - 'a']++;

            // 窗口超过p的长度时，移出最左侧字符
            if (right >= m) {
                window[s[right - m] - 'a']--;
            }

            // 只有窗口长度达到m时，才有可能成为字母异位词
            if (right >= m - 1 && window == need) {
                result.push_back(right - m + 1);
            }
        }

        return result;
    }
};

复杂度分析

• 时间复杂度：O(n + m)。统计 p 需要 O(m)，右指针遍历 s 需要 O(n)；每次比较 26 个位置是固定常数。
• 空间复杂度：O(1)。两个频次数组的长度始终为 26，不随输入规模变化。

其他语言

Python3

from typing import List


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n, m = len(s), len(p)
        if m > n:
            return []

        need = [0] * 26
        window = [0] * 26
        for ch in p:
            need[ord(ch) - ord('a')] += 1

        result = []
        for right, ch in enumerate(s):
            window[ord(ch) - ord('a')] += 1

            if right >= m:
                left_ch = s[right - m]
                window[ord(left_ch) - ord('a')] -= 1

            if right >= m - 1 and window == need:
                result.append(right - m + 1)

        return result

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n = s.length();
        int m = p.length();
        List<Integer> result = new ArrayList<>();

        if (m > n) return result;

        int[] need = new int[26];
        int[] window = new int[26];
        for (char c : p.toCharArray()) {
            need[c - 'a']++;
        }

        for (int right = 0; right < n; right++) {
            window[s.charAt(right) - 'a']++;

            if (right >= m) {
                window[s.charAt(right - m) - 'a']--;
            }

            if (right >= m - 1 && Arrays.equals(window, need)) {
                result.add(right - m + 1);
            }
        }

        return result;
    }
}

Go

func findAnagrams(s string, p string) []int {
    n, m := len(s), len(p)
    result := make([]int, 0)

    if m > n {
        return result
    }

    var need [26]int
    var window [26]int
    for i := 0; i < m; i++ {
        need[p[i]-'a']++
    }

    for right := 0; right < n; right++ {
        window[s[right]-'a']++

        if right >= m {
            window[s[right-m]-'a']--
        }

        // Go中的定长数组可以直接比较
        if right >= m-1 && window == need {
            result = append(result, right-m+1)
        }
    }

    return result
}

JS

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    const n = s.length;
    const m = p.length;
    if (m > n) return [];

    const need = new Array(26).fill(0);
    const window = new Array(26).fill(0);
    const codeA = 'a'.charCodeAt(0);

    for (const ch of p) {
        need[ch.charCodeAt(0) - codeA]++;
    }

    const sameFrequency = () => {
        for (let i = 0; i < 26; i++) {
            if (window[i] !== need[i]) return false;
        }
        return true;
    };

    const result = [];
    for (let right = 0; right < n; right++) {
        window[s.charCodeAt(right) - codeA]++;

        if (right >= m) {
            window[s.charCodeAt(right - m) - codeA]--;
        }

        if (right >= m - 1 && sameFrequency()) {
            result.push(right - m + 1);
        }
    }

    return result;
};

与代码随想录联系

这道题把两个常见套路连在了一起：

• 判断两个字符串是不是字母异位词，对应哈希表章节的 242.有效的字母异位词
• 维护连续区间，对应数组章节的 209.长度最小的子数组

本题还可以和 Hot100 中的 49.字母异位词分组、76.最小覆盖子串 一起学习。

49 题关注的是“如何表示字母异位词的共同特征”，76 题使用的是满足条件后不断收缩的可变窗口，而本题使用的是长度始终等于 p.length() 的定长窗口。把这三道题放在一起对比，哈希表和滑动窗口的使用边界就清楚了。