LeetCode LCR 015. 找到字符串中所有字母异位词
题目描述
题意分析
找出字符串
s中所有与p互为字母异位词的连续子串，返回它们的起始下标。异位词可以改变字母排列顺序，但每个字母的出现次数必须保持一致，所以候选长度固定为p.length()。这里要收集全部位置，找到一个后仍需继续寻找；匹配窗口可以互相重叠，也可以具有完全相同的内容，只要起点不同就分别记录。两串都只含小写英文字母，源串短于目标串时返回空结果。
解法：定长窗口收集匹配起点
核心思路
[!blue]
设源串长度为
m，目标长度为n。用cnt2固定保存p的字符频次，用cnt1保存s中当前长度为n的窗口频次。两个数组逐项相等，就等价于当前窗口是目标的一个异位词。相邻窗口有
n - 1个位置重合，右移一次只改变两个字符：新右端加入，旧左端离开。初始统计前n个字符后，每次增减这两个计数即可维持准确的窗口频次，无需重新扫描窗口内容。当新右端为
i时，移出的旧位置是i - n，新窗口覆盖[i - n + 1, i]，所以匹配时要保存i - n + 1。它是新左端，不是被移出的下标，也不是当前右端。初始窗口单独检查并可能记录零；后续每次只移动一位，确保重叠匹配也不会被跳过。找到一个后只是追加答案，不提前返回，不改变频次状态，继续扫描其他起点。最终结果自然按起点递增排列。
解题步骤
- 创建答案列表，若
s比p短，直接返回空结果。- 统计
p与s的首个等长窗口的频次。- 比较首窗口，匹配则加入起点零。
- 从新右端下标
i = n开始，每次加入s[i]并移除s[i - n]。- 两次计数修改完成后比较数组，匹配时追加起点
i - n + 1。- 扫描所有窗口后返回全部起点。
代码实现
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int m = s.length();
int n = p.length();
List<Integer> answer = new ArrayList<>();
// 长度不够时无解，同时防止建初始窗口越界。
if (m < n) {
return answer;
}
int[] cnt1 = new int[26];
int[] cnt2 = new int[26];
for (int i = 0; i < n; ++i) {
++cnt1[s.charAt(i) - 'a'];
++cnt2[p.charAt(i) - 'a'];
}
// 起点为 0 的窗口也是候选。
if (Arrays.equals(cnt1, cnt2)) {
answer.add(0);
}
for (int i = n; i < m; ++i) {
// 右端进、左端出，两次更新后窗口长度回到 n。
++cnt1[s.charAt(i) - 'a'];
--cnt1[s.charAt(i - n) - 'a'];
if (Arrays.equals(cnt1, cnt2)) {
// 窗口覆盖 [i - n + 1, i]，起点是 i - n + 1。
answer.add(i - n + 1);
}
}
return answer;
}
}
func findAnagrams(s string, p string) (answer []int) {
m, n := len(s), len(p)
if m < n {
return
}
// 定长数组是值类型，可直接用 == 整体比较。
var cnt1, cnt2 [26]int
for i, ch := range p {
cnt1[s[i]-'a']++
cnt2[ch-'a']++
}
if cnt1 == cnt2 {
answer = append(answer, 0)
}
for i := n; i < m; i++ {
cnt1[s[i]-'a']++
cnt1[s[i-n]-'a']--
if cnt1 == cnt2 {
answer = append(answer, i-n+1)
}
}
return
}
复杂度分析
- 时间复杂度：
O(n + 26m)，即O(m + n)。初始统计目标长度的字符，每个后续窗口只增减两个计数并比较固定二十六项。- 空间复杂度：辅助空间
O(1)；答案在最坏情况下包含线性数量的起点，另占O(m)。
关键点总结
[!green]
- 精确频次匹配保证异位词成立，固定窗口保证长度一致。
- 窗口起点由闭区间长度推得
i - n + 1。- 每次仅移动一位，既覆盖分离匹配，也覆盖重叠匹配。
- 收集全部解与判断存在性的区别在于命中后追加并继续。
易错点总结
[!yellow]
- 记录右端或旧左端：需要的是新窗口起点
i - n + 1。- 第一次匹配就返回：后面仍可能有合法起点。
- 匹配后跨过整个窗口：会跳过与当前窗口重叠的其他答案。
- 只比较字母集合：各字母数量也必须与目标一致。
- 忘记首窗口检查或移出旧字符：前者漏掉起点零，后者会把计数变成不断增长的前缀。
- 对匹配内容去重：题目返回位置，同内容的不同起点仍然是不同答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 567. 字符串的排列 | 中等 | 同样比较定长窗口的频次，本题记录全部匹配位置，原题只回答是否存在。 |
| 49. 字母异位词分组 | 中等 | 同样识别字母频次相同的字符串，原题按完整单词分组，本题滑动截取子串。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！