LC 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]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

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

---

双指针（滑动窗口）

这是一道使用双指针实现滑动窗口的裸题。

具体的，我们可以先创建一个大小为 $26$ 的数组 $c2$ 来统计字符串 p 的词频，另外一个同等大小的数组 $c1$ 用来统计「滑动窗口」内的 s 的子串词频。

当两个数组所统计词频相等，说明找到了一个异位组，将窗口的左端点加入答案。

Java 代码：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int n = s.length(), m = p.length();
        int[] c1 = new int[26], c2 = new int[26];
        for (int i = 0; i < m; i++) c2[p.charAt(i) - 'a']++;
        for (int l = 0, r = 0; r < n; r++) {
            c1[s.charAt(r) - 'a']++;
            if (r - l + 1 > m) c1[s.charAt(l++) - 'a']--;
            if (check(c1, c2)) ans.add(l);
        }
        return ans;
    }
    boolean check(int[] c1, int[] c2) {
        for (int i = 0; i < 26; i++) {
            if (c1[i] != c2[i]) return false;
        }
        return true;
    }
}

C++ 代码：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        int n = s.size(), m = p.size();
        if (n < m) return ans;
        vector<int> c1(26, 0), c2(26, 0);
        for (char c : p) c2[c - 'a']++;
        for (int l = 0, r = 0; r < n; r++) {
            c1[s[r] - 'a']++;
            if (r - l + 1 > m) c1[s[l++] - 'a']--;
            if (c1 == c2) ans.push_back(l);
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans = []
        n, m = len(s), len(p)
        if n < m:
            return ans
        c1, c2 = [0] * 26, [0] * 26
        for c in p:
            c2[ord(c) - ord('a')] += 1
        l = 0
        for r in range(n):
            c1[ord(s[r]) - ord('a')] += 1
            if r - l + 1 > m:
                c1[ord(s[l]) - ord('a')] -= 1
                l += 1
            if c1 == c2:
                ans.append(l)
        return ans

TypeScript 代码：

function check(a: number[], b: number[]): boolean {
    for (let i = 0; i < 26; i++) {
        if (a[i] !== b[i]) return false;
    }
    return true;
}
function findAnagrams(s: string, p: string): number[] {
    const ans = [];
    const n = s.length, m = p.length;
    if (n < m) return ans;
    const c1 = new Array(26).fill(0), c2= new Array(26).fill(0);
    for (let i = 0; i < m; i++) c2[p.charCodeAt(i) - 'a'.charCodeAt(0)]++;    
    for (let l = 0, r = 0; r < n; r++) {
        c1[s.charCodeAt(r) - 'a'.charCodeAt(0)]++;
        if (r - l + 1 > m) {
            c1[s.charCodeAt(l) - 'a'.charCodeAt(0)]--;
            l++;
        }
        if (check(c1, c2)) ans.push(l);
    }
    return ans;
};

• 时间复杂度：令 s 和 p 的长度分别为 $n$ 和 $m$，$C = 26$ 为字符集大小。统计 p 词频（构建 $c2$ 数组）的复杂度为 $O(m)$；使用双指针检查 s 串的复杂度为 $O(C \times n)$。整体复杂度为 $O(C*n + m)$
• 空间复杂度：$O(C)$

---

优化 check

解法一中每次对滑动窗口的检查都不可避免需要检查两个词频数组，复杂度为 $O(C)$。

事实上，我们只关心两个数组是否完全一致，因而我们能够只维护一个词频数组 $cnt$ 来实现。

起始处理 p 串时，只对 $cnt$ 进行词频字符自增操作。当处理 s 的滑动窗口子串时，尝试对 $cnt$ 中的词频进行「抵消/恢复」操作：

• 当滑动窗口的右端点右移时（增加字符），对 $cnt$ 执行右端点字符的「抵消」操作；
• 当滑动窗口的左端点右移时（减少字符），对 $cnt$ 执行左端点字符的「恢复」操作。

同时，使用变量 $a$ 统计 p 中不同字符的数量，使用变量 $b$ 统计滑动窗口（子串）内有多少个字符词频与 $p$ 相等。

当滑动窗口移动（ 执行「抵消/恢复」）时，如果「抵消」后该字符词频为 $0$，说明本次右端点右移，多产生了一位词频相同的字符；如果「恢复」后该字符词频数量为 $1$，说明少了一个为词频相同的字符。当且仅当 $a = b$ 时，我们找到了一个新的异位组。

Java 代码：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int n = s.length(), m = p.length();
        int[] cnt = new int[26];
        for (int i = 0; i < m; i++) cnt[p.charAt(i) - 'a']++;
        int a = 0;
        for (int i = 0; i < 26; i++) if (cnt[i] != 0) a++;
        for (int l = 0, r = 0, b = 0; r < n; r++) {
            // 往窗口增加字符，进行词频的抵消操作，如果抵消后词频为 0，说明有一个新的字符词频与 p 完全相等
            if (--cnt[s.charAt(r) - 'a'] == 0) b++; 
            // 若窗口长度超过规定，将窗口左端点右移，执行词频恢复操作，如果恢复后词频为 1（恢复前为 0），说明少了一个词频与 p 完全性相等的字符
            if (r - l + 1 > m && ++cnt[s.charAt(l++) - 'a'] == 1) b--;
            if (b == a) ans.add(l);
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        int n = s.size(), m = p.size();
        if (n < m) return ans;
        vector<int> cnt(26, 0);
        for (char c : p) cnt[c - 'a']++;
        int a = 0;
        for (int i = 0; i < 26; i++) if (cnt[i] != 0) a++;        
        for (int l = 0, r = 0, b = 0; r < n; r++) {
            int rIdx = s[r] - 'a';
            if (--cnt[rIdx] == 0) b++;
            if (r - l + 1 > m && ++cnt[s[l++] - 'a'] == 1) b--;
            if (b == a) ans.push_back(l);
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans = []
        n, m = len(s), len(p)
        if n < m:
            return ans
        cnt = [0] * 26
        for c in p:
            cnt[ord(c) - ord('a')] += 1
        a = sum(1 for x in cnt if x != 0)
        b = l = 0
        for r in range(n):
            r_idx = ord(s[r]) - ord('a')
            cnt[r_idx] -= 1
            if cnt[r_idx] == 0:
                b += 1
            if r - l + 1 > m:
                l_idx = ord(s[l]) - ord('a')
                cnt[l_idx] += 1
                if cnt[l_idx] == 1:
                    b -= 1
                l += 1
            if b == a:
                ans.append(l)
        return ans

TypeScript 代码：

function findAnagrams(s: string, p: string): number[] {
    const ans = [];
    const n = s.length, m = p.length;
    if (n < m) return ans;
    const cnt = new Array(26).fill(0);
    for (let i = 0; i < m; i++) cnt[p.charCodeAt(i) - 'a'.charCodeAt(0)]++;
    let a = 0;
    for (let i = 0; i < 26; i++) if (cnt[i] !== 0) a++;
    for (let l = 0, r = 0, b = 0; r < n; r++) {
        const rIdx = s.charCodeAt(r) - 'a'.charCodeAt(0);
        if (--cnt[rIdx] === 0) b++;
        if (r - l + 1 > m && ++cnt[s.charCodeAt(l++) - 'a'.charCodeAt(0)] === 1) b--;
        if (b === a) ans.push(l);
    }
    return ans;
};

• 时间复杂度：令 s 和 p 的长度分别为 $n$ 和 $m$，$C = 26$ 为字符集大小。构造 $cnt$ 的复杂度为 $O(m)$，统计 $p$ 中不同的字符数量为 $O(C)$，对 s 进行滑动窗口扫描得出答案的复杂度为 $O(n)$。整体复杂度为 $O(m + C + n)$
• 空间复杂度：$O(C)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.438 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。