Skip to main content

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

给定两个字符串 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" 的异位词。

简单做法：先把p排序，然后转Set, 遍历s，若p存在当前字符，从字符位置截取和p长度的子串然后排序，和排序p相等则符合，不相等不符合，继续遍历。（缺点p不能包含重复字符）

进阶做法：使用滑动窗口和哈希表来高效地解决这个问题。异位词的特点是字符种类和数量完全相同，因此我们可以通过比较滑动窗口内的字符频率与 p 的字符频率来判断是否为异位词。

方法思路​

  1. 统计字符频率：首先统计 p 中每个字符的出现次数，存储在哈希表 pCount 中。
  2. 初始化滑动窗口：使用固定大小的窗口（长度为 p.length）在 s 上滑动，统计窗口内的字符频率。
  3. 比较频率：每次滑动窗口后，比较窗口内的字符频率与 p 的字符频率是否相同。若相同，则记录窗口起始索引。

代码实现​

function findAnagrams(s, p) {
    const result = [];
    const pLength = p.length;
    const sLength = s.length;
    
    if (sLength < pLength) return result; // 若s长度小于p，直接返回空数组
    
    // 统计p中字符频率
    const pCount = new Array(26).fill(0);
    for (const char of p) {
        pCount[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    // 初始化滑动窗口频率
    const windowCount = new Array(26).fill(0);
    for (let i = 0; i < pLength; i++) {
        windowCount[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    // 比较初始窗口
    if (arraysEqual(windowCount, pCount)) {
        result.push(0);
    }
    
    // 滑动窗口
    for (let i = pLength; i < sLength; i++) {
        // 移除窗口左侧字符
        windowCount[s[i - pLength].charCodeAt(0) - 'a'.charCodeAt(0)]--;
        // 添加窗口右侧字符
        windowCount[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
        
        // 比较当前窗口与p的频率
        if (arraysEqual(windowCount, pCount)) {
            result.push(i - pLength + 1);
        }
    }
    
    return result;
}

// 辅助函数：比较两个数组是否相等
function arraysEqual(a, b) {
    if (a.length !== b.length) return false;
    for (let i = 0; i < a.length; i++) {
        if (a[i] !== b[i]) return false;
    }
    return true;
}

代码解释​

  1. 统计字符频率：使用长度为26的数组 pCount 记录 p 中每个字符的出现次数。
  2. 初始化窗口：创建同样大小的数组 windowCount，并统计初始窗口（前 p.length 个字符）的频率。
  3. 滑动窗口：
    • 每次滑动时，移除窗口左侧字符的计数，添加窗口右侧字符的计数。
    • 使用辅助函数 arraysEqual 比较当前窗口与 p 的字符频率是否相同。
  4. 记录结果：若频率相同，记录窗口的起始索引。

复杂度分析​

  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度。每个字符仅被访问两次（添加和移除窗口）。
  • 空间复杂度：O(1)，因为使用固定大小的数组（26个字符）来存储频率。

优化思路​

如果字符集较大（如Unicode字符），可以使用哈希表代替固定数组，并维护一个计数器来记录窗口中匹配的字符种类数，进一步优化比较效率。但对于本题的约束条件，上述方法已经足够高效。