当前位置：首页 > web >正文

LeetCode LCR 015. 找到字符串中所有字母异位词 (Java)

web 2025/5/16 6:49:49

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

题目描述

给定两个字符串 s 和 p，要求找到 s 中所有是 p 的变位词（字母相同但排列不同）的子串，并返回这些子串的起始索引。例如：

输入 s = "cbaebabacd", p = "abc"，输出 [0, 6]，因为子串 "cba" 和 "bac" 是 "abc" 的变位词。
输入 s = "abab", p = "ab"，输出 [0, 1, 2]，因为每个长为 2 的子串都是 "ab" 的变位词。

初始思路：暴力滑动窗口

核心思想

固定窗口长度：窗口长度为 p.length()，逐个遍历 s 中所有可能的窗口。
统计字符频率：对每个窗口，统计字符出现次数，与 p 的字符频率比对。
记录匹配结果：若窗口字符频率与 p 完全一致，记录当前窗口的起始索引。

代码实现

public static List<Integer> findAnagrams_2(String s, String p) {int windowLen = p.length();List<Integer> result = new ArrayList<>();int[] pCount = new int[26];// 统计 p 的字符频率for (char c : p.toCharArray()) {pCount[c - 'a']++;}for (int left = 0; left <= s.length() - windowLen; left++) {int[] sCount = new int[26];int sign = 1;// 统计当前窗口的字符频率for (int j = left; j < left + windowLen; j++) {sCount[s.charAt(j) - 'a']++;}// 比对频率是否一致for (int j = 0; j < 26; j++) {if (sCount[j] != pCount[j]) {sign = 0;break; // 优化点：发现不一致立即跳出}}if (sign == 1) {result.add(left);}}return result;
}

复杂度分析

时间复杂度：O(n * m)，其中 n 是 s 的长度，m 是 p 的长度。每次窗口需要遍历 m 个字符，共遍历 n - m + 1 次。
空间复杂度：O(1)，固定使用两个长度为 26 的数组。

优化思路：动态滑动窗口

核心改进

减少重复计算：维护一个固定长度的窗口，每次移动窗口时，只需更新移除的字符和新增的字符。
差异计数器：通过一个变量记录当前窗口与 p 的频率差异，避免每次全量比对。

优化代码

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];int windowLen = p.length();// 初始化 p 的字符频率和第一个窗口的 s 字符频率for (int i = 0; i < windowLen; i++) {pCount[p.charAt(i) - 'a']++;sCount[s.charAt(i) - 'a']++;}int diff = 0;for (int i = 0; i < 26; i++) {if (sCount[i] != pCount[i]) diff++;}if (diff == 0) result.add(0);// 滑动窗口：逐个右移，动态更新频率和差异for (int right = windowLen; right < s.length(); right++) {int leftChar = s.charAt(right - windowLen) - 'a';int rightChar = s.charAt(right) - 'a';// 移除左边界字符if (sCount[leftChar] == pCount[leftChar]) diff++;sCount[leftChar]--;if (sCount[leftChar] == pCount[leftChar]) diff--;// 添加右边界字符if (sCount[rightChar] == pCount[rightChar]) diff++;sCount[rightChar]++;if (sCount[rightChar] == pCount[rightChar]) diff--;if (diff == 0) {result.add(right - windowLen + 1);}}return result;
}