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

题目描述

这是 LeetCode 上的 438. 找到字符串中所有字母异位词 ，难度为 中等。

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

1
2
3
4
5
6
7
输入: s = "cbaebabacd", p = "abc"

输出: [0,6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:
1
2
3
4
5
6
7
8
输入: 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 仅包含小写字母

双指针（滑动窗口）

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

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

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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
}

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

优化 check

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

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

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

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

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

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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
    }
}

  • 时间复杂度：令 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 原题链接和其他优选题解。