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. 异位词的特性：

   • 两个字符串是异位词意味着它们的字符数量完全一致。换句话说，两个字符串的字符频率分布是相同的。

2. 滑动窗口：

   • 使用滑动窗口在字符串 s 上构造一个长度为 p.length 的窗口。
   • 维护窗口内的字符频率，与目标字符串 p 的字符频率进行比较。

3. 实现步骤：

   1. 构造目标字符串 p 的字符频率统计数组。
   2. 在字符串 s 上滑动窗口，每次向右移动一个字符，更新当前窗口的字符频率统计数组。
   3. 比较当前窗口的频率数组和目标频率数组，如果相同，则记录起始索引。
   4. 重复上述过程直到滑动窗口遍历完整个字符串。

---

代码实现

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read strings s and p
        String s = scanner.nextLine();
        String p = scanner.nextLine();

        Solution solution = new Solution();
        List<Integer> result = solution.findAnagrams(s, p);

        // Print result list
        System.out.println(result);
        scanner.close();
    }
}

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) {
            return result;
        }

        // 字符频率数组
        int[] pCount = new int[26];
        int[] sCount = new int[26];

        // 统计目标字符串 p 的字符频率
        for (char c : p.toCharArray()) {
            pCount[c - 'a']++;
        }

        // 初始化窗口的字符频率
        for (int i = 0; i < p.length(); i++) {
            sCount[s.charAt(i) - 'a']++;
        }

        // 滑动窗口遍历字符串 s
        for (int i = 0; i <= s.length() - p.length(); i++) {
            // 比较当前窗口和目标频率数组
            if (isAnagram(sCount, pCount)) {
                result.add(i); // 记录起始索引
            }

            // 滑动窗口向右移动
            if (i + p.length() < s.length()) {
                sCount[s.charAt(i) - 'a']--; // 移除窗口最左侧字符
                sCount[s.charAt(i + p.length()) - 'a']++; // 添加窗口最右侧字符
            }
        }

        return result;
    }

    // 判断两个字符频率数组是否相等
    private boolean isAnagram(int[] sCount, int[] pCount) {
        for (int i = 0; i < 26; i++) {
            if (sCount[i] != pCount[i]) {
                return false;
            }
        }
        return true;
    }
}

---

时间复杂度分析

1. 时间复杂度：

   • 遍历目标字符串 p 构造频率数组，时间复杂度为 O(p.length)。
   • 遍历字符串 s 的所有窗口，每次比较字符频率数组需要常数时间，时间复杂度为 O(s.length)。
   • 总时间复杂度为 O(s.length + p.length)。

2. 空间复杂度：

   • 使用了两个固定大小的频率数组，空间复杂度为 O(1)。

---

总结

• 通过滑动窗口和频率数组的比较，可以高效地解决字母异位词的查找问题。
• 此解法兼顾了时间复杂度和空间复杂度，是一种高效的实现方式。

如果有任何疑问，欢迎提问！