【LC100】No438. 找到字符串中所有字母异位词

题目描述

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

提示:

• 1 <= s.length, p.length <= 3 * 104

• 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" 的异位词。

链接

思路

在 s 中找 p 的字母异位词，p 是已知的。

所以本题的特点是：

• 连续子串，也就是连续区间

• 需要考虑字母出现次数

以上，所以这是一个很典型的滑动窗口问题。

解法一：定长滑动窗口

由于 p 是已知的，长度固定，我们首先想到的是在 s 中创建一个定长的滑动窗口，依次寻找符合题意的子串。

对于判断 s 中滑动窗口的子串和 p 是否为异位词，我们用两个数组来处理。

分别记录 s 中滑动窗口的子串出现的字符和次数，以及 p 中出现的字符和次数，然后比较两个数组是否相等即可。

枚举窗口右端点，通过 p 的长度来确定窗口左端点。

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (s == null || p == null || s.length() < p.length()) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        int[] sNum = new int[26];
        int[] pNum = new int[26];
        for (char c : p.toCharArray()) {
            pNum[c - 'a']++;
        }
        for (int right = 0; right < s.length(); right++) {
            sNum[s.charAt(right) - 'a']++;
            // 维护一个定长窗口
            int left = right - p.length() + 1;
            if (left < 0) {
                continue;
            }
            // 窗口中s的子串和p包含的字母和出现次数相等
            if (Arrays.equals(sNum, pNum)) {
                res.add(left);
            }
            // 定长窗口右移：左指针先右移，因为下次循环进入时会找到新的右指针，又会计算新的左指针
            sNum[s.charAt(left) - 'a']--;
        }

        return res;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)

解法二：变长滑动窗口

为什么还有一个变长的解法，因为这个类似于通解。感觉对于本题并没有什么显著优化的提升。

定长可以做，那么变长滑动窗口同样可以做。（告诉lc，俺不是孬种

通过使用一个 int[] 数组，减少空间使用。（更简洁了，但也更抽象了

先在数组中存储 p 的各个字符出现次数，然后对于 s 中滑动窗口，在进入窗口时，将指针指向的字母出现次数 -1。

比较巧妙的一个判断是：

• 当 s 中滑动窗口中的某个字母出现次数比 p 中多时，次数 -1 会减至负数。此时不符合题意，应该移动窗口。

• 当 s 中滑动窗口中出现了 p 中不存在的字母时，次数原本是 0，-1 后也会减至负数。此时不符合题意，应该移动窗口。（此时 num[rightNum] == -1，while 循环会一直执行，left++ 直到 left 指向 right 时，num[rightNum]++ 回到 0，此时，left 指向了 right+1）

最后比较滑动窗口长度和 p 的长度，即可判断是否相等。

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (s == null || p == null || s.length() < p.length()) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        int[] num = new int[26];
        for (char c : p.toCharArray()) {
            num[c - 'a']++;
        }
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            int rightNum = s.charAt(right) - 'a';
            num[rightNum]--;
            // 1：处理出现重复字母：进入循环代表right指向的字母重复了，从左边缩小窗口
            // 2：处理处理不在p中的字母：循环会一直运行，直到left移动到right+1
            while (num[rightNum] < 0) {
                num[s.charAt(left) - 'a']++;
                left++;
            }
            if (right - left + 1 == p.length()) {
                res.add(left);
            }
        }
        return res;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)

总结

1. 处理字母频次问题，可以创建一个数组存储出现次数：只有字母为int[26]，所有字符为int[128]。

2. 不同窗口的思路。

定长滑动窗口，是窗口长度一定固定，考虑每次移动产生的新窗口和 p 是否是异位词即可。

变长滑动窗口，是找到和 p 是异位词的窗口，考虑窗口长度和 p 是否一样即可。