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

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 * 104
• s 和 p 仅包含小写字母

题解思路

初始化变量：

• 创建一个 list 用于存储所有找到的子串的起始位置。
• 如果 s 的长度小于 p 的长度，直接返回空列表，因为不可能存在任何字母异位词。
• 创建两个频率数组 pFreq 和 sFreq，分别用来存储字符串 p 和当前滑动窗口的字符频率。

填充 p 的字符频率：

• 遍历字符串 p 中的每个字符，并在 pFreq 数组中对应位置上增加计数。pFreq[c - 'a']++ 这一步是将字符转换为字母的索引（’a’ 对应 0，’b’ 对应 1，依此类推）。

初始化滑动窗口：

• 使用一个大小为 p.length() 的滑动窗口，初始化窗口的字符频率。遍历字符串 s 的前 p.length() 个字符，并更新 sFreq 数组。

比较初始窗口与 p 的字符频率：

• 如果初始窗口（即字符串 s 的前 p.length() 个字符）的字符频率与 p 的字符频率相同，说明当前窗口是一个异位词，将 0（起始位置）加入 list。

滑动窗口：

• 从 p.length() 开始，逐步向右滑动窗口。对于每个新的字符 s[end]，begin = end - p.length()执行以下操作：

1. 增加当前字符 s[end] 的频率。
2. 减少窗口左侧字符 s[begin] 的频率，begin 是当前窗口的起始位置。
3. 比较 sFreq 和 pFreq，如果两者相等，说明当前窗口是 p 的一个异位词，将 begin + 1（当前窗口的起始位置）加入 list。

• 每次滑动窗口，begin 和 end 更新为新的窗口边界。

返回结果：

• 最终返回 list，其中包含所有符合条件的子串的起始位置。

题解代码

// 定义一个对象比较是否是字母异位词,耗时时间长，性能不高
static class Data {
    private final int[] data = new int[26];

    public Data(String c) {
        for (int i = 0; i < c.length(); i++) {
            data[c.charAt(i) - 97]++;
        }
    }

    @Override
    public boolean equals(Object object) {
        if (this == object) return true;
        if (object == null || getClass() != object.getClass()) return false;
        Data data1 = (Data) object;
        return Objects.deepEquals(data, data1.data);
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(data);
    }
}

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> list = new ArrayList<>();
    // 如果s的长度比p的长度还小，直接返回
    if (s.length() < p.length()) return list;
    // 创建字符串p的Data对象
    Data pData = new Data(p);
    // 定义窗口大小
    int begin = 0;
    int end = p.length();
    while (end <= s.length()) {
        // 截取窗口内的字符串
        String substring = s.substring(begin, end);
        Data subData = new Data(substring);
        // 比较窗口内的字符串于字符串p是否是字母异位词
        if (subData.equals(pData)) {
            list.add(begin);
        }
        // 移动窗口
        begin++;
        end++;
    }
    return list;
}

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> list = new ArrayList<>();
    if (s.length() < p.length()) return list;
    // 创建字符频率数组
    int[] pFreq = new int[26];  // p字符串的字符频率
    int[] sFreq = new int[26];  // 当前滑动窗口的字符频率
    // 填充 p 字符串的频率
    for (char c : p.toCharArray()) {
        pFreq[c - 'a']++;
    }
    // 初始化滑动窗口
    for (int i = 0; i < p.length(); i++) {
        sFreq[s.charAt(i) - 'a']++;
    }
    // 如果窗口的字符频率与 p 的字符频率相同，记录起始位置
    if (Arrays.equals(pFreq, sFreq)) {
        list.add(0);
    }
    // 滑动窗口
    for (int end = p.length(); end < s.length(); end++) {
        int begin = end - p.length();
        // 新增字符
        sFreq[s.charAt(end) - 'a']++;
        // 移除旧字符
        sFreq[s.charAt(begin) - 'a']--;
        // 比较窗口和 p 的字符频率
        if (Arrays.equals(pFreq, sFreq)) {
            list.add(begin + 1); // 新的窗口的begin需要+1
        }
    }
    return list;
}