.jpg)
1007 字
5 分钟
找到字符串中所有字母异位词
题目描述
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
解题思路
- 滑动窗口法：
- 初始化两个频率数组（长度26）存储字符计数
- 先记录模式p的字符频率
- 初始化窗口为s的前p长度个字符
- 窗口滑动：
- 每次右移窗口：左边界字符计数减1，右边界字符计数加1
- 比较当前窗口频率与模式频率
- 若匹配则记录起始索引
- 频率匹配：
- 使用常数时间比较频率数组
- 避免重新扫描整个窗口
- 边界处理：
- 处理空字符串和短于p的s
- 字符索引映射：charCodeAt() - 97
关键洞察
- 异位词本质：
- 字符组成完全相同（频率一致）
- 与顺序无关
- 频率数组优势：
- 替代昂贵的子串排序操作
- 常数时间完成频率比较
- 滑动窗口效率：
- 窗口平移时只更新两个字符的计数
- 避免O(n×m)的暴力扫描
- 字符索引优化：
- 字母映射到0-25的整数索引
- 直接访问数组元素
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n)：n为s长度，每个字符处理两次（进/出） |
| 空间复杂度 | O(1)：固定大小频率数组（26×2） |
代码实现
/** * @link {https://leetcode.cn/problems/find-all-anagrams-in-a-string/} * @param {string} s * @param {string} p * @return {number[]} */const findAnagrams = (s, p) => { if (s.length < p.length) return [];
const pLen = p.length; const sLen = s.length; const result = [];
// 初始化频率数组（26个字母） const pCount = new Array(26).fill(0); const winCount = new Array(26).fill(0);
// 记录模式p的频率 for (let i = 0; i < pLen; i++) { pCount[p.charCodeAt(i) - 97]++; }
// 初始化窗口频率 for (let i = 0; i < pLen; i++) { winCount[s.charCodeAt(i) - 97]++; }
// 比较初始窗口 if (arrayEqual(pCount, winCount)) { result.push(0); }
// 滑动窗口遍历 for (let i = pLen; i < sLen; i++) { // 移除左边界字符 winCount[s.charCodeAt(i - pLen) - 97]--; // 添加右边界字符 winCount[s.charCodeAt(i) - 97]++;
// 比较频率 if (arrayEqual(pCount, winCount)) { result.push(i - pLen + 1); } }
return result;};
// 常数时间频率数组比较const arrayEqual = (arr1, arr2) => { for (let i = 0; i < 26; i++) { if (arr1[i] !== arr2[i]) return false; } return true;};/** * @param {string} s * @param {string} p * @return {number[]} */var findAnagrams = function (s, p) { const sLen = s.length; const pLen = p.length;
if (sLen < pLen) return [];
const result = []; const count = new Array(26).fill(0); const aCharCode = 'a'.charCodeAt(); // 预计算 'a' 的编码
// 初始化窗口：统计s前pLen个字符和p的字符差异 for (let i = 0; i < pLen; i++) { count[s.charCodeAt(i) - aCharCode]++; count[p.charCodeAt(i) - aCharCode]--; }
// 计算初始差异数 let differ = 0; for (let i = 0; i < 26; i++) { if (count[i] !== 0) differ++; }
if (differ === 0) result.push(0);
// 滑动窗口：每次移动一位 for (let i = 0; i < sLen - pLen; i++) { const leftChar = s.charCodeAt(i) - aCharCode; const rightChar = s.charCodeAt(i + pLen) - aCharCode;
// 处理左边界移出的字符 if (count[leftChar] === 1) { differ--; // 从1变0，差异减少 } else if (count[leftChar] === 0) { differ++; // 从0变-1，差异增加 } count[leftChar]--;
// 处理右边界移入的字符 if (count[rightChar] === -1) { differ--; // 从-1变0，差异减少 } else if (count[rightChar] === 0) { differ++; // 从0变1，差异增加 } count[rightChar]++;
// 差异为0表示找到异位词 if (differ === 0) result.push(i + 1); }
return result;};算法执行流程
输入: s="cbaebabacd", p="abc"
步骤:1. p频率: [a:1,b:1,c:1] → [1,1,1,0,...]2. 初始窗口s[0:2]="cba" → [1,1,1,0,...] → 匹配 → 记录03. 窗口右移: - 移除s[0]='c' → [1,1,0,...] - 添加s[3]='e' → [1,1,0,1,...] → 不匹配4. 继续右移: - ...直到窗口"bae"→"bab"→"bac" - s[6:8]="bac" → [1,1,1,0,...] → 匹配 → 记录6实际应用场景
- 生物信息学：
// DNA序列中查找相似基因片段// s="ATCGAATTCG", p="AATT" → 位置[4]`- 文本搜索：
// 文档中查找变位词（如"listen"和"silent"）`- 密码分析：
// 检测密文中的预设模式