Medium

题目描述

给定两个字符串 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 <= s.length, p.length <= 3 * 10^4
  • s 和 p 仅包含小写英文字母

解题思路

这道题是经典的滑动窗口问题，需要找出字符串 s 中所有与 p 为字母异位词的子串起始位置。

核心思路：

  1. 使用固定长度的滑动窗口，窗口大小为 p 的长度
  2. 维护窗口内字符频次，判断是否与 p 的字符频次相等

具体算法：

  • 首先统计字符串 p 中各字符的频次
  • 使用长度为 p.length 的滑动窗口在 s 上移动
  • 维护窗口内字符频次：添加右边界字符，移除左边界字符
  • 当窗口内字符频次与 p 的频次完全相等时，记录起始位置

优化点：

  • 使用数组代替哈希表存储字符频次（因为只有26个小写字母）
  • 维护一个 match 计数器，记录频次匹配的字符种类数，避免每次都比较整个频次数组

时间复杂度为 O(|s|)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        if (s.length() < p.length()) return result;
        
        vector<int> pCount(26, 0), windowCount(26, 0);
        
        // 统计p中字符频次
        for (char c : p) {
            pCount[c - 'a']++;
        }
        
        // 初始化窗口
        for (int i = 0; i < p.length(); i++) {
            windowCount[s[i] - 'a']++;
        }
        
        // 检查初始窗口
        if (pCount == windowCount) {
            result.push_back(0);
        }
        
        // 滑动窗口
        for (int i = p.length(); i < s.length(); i++) {
            // 添加新字符
            windowCount[s[i] - 'a']++;
            // 移除旧字符
            windowCount[s[i - p.length()] - 'a']--;
            
            // 检查是否匹配
            if (pCount == windowCount) {
                result.push_back(i - p.length() + 1);
            }
        }
        
        return result;
    }
};

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):
            return []
        
        result = []
        p_count = [0] * 26
        window_count = [0] * 26
        
        # 统计p中字符频次
        for c in p:
            p_count[ord(c) - ord('a')] += 1
        
        # 初始化窗口
        for i in range(len(p)):
            window_count[ord(s[i]) - ord('a')] += 1
        
        # 检查初始窗口
        if p_count == window_count:
            result.append(0)
        
        # 滑动窗口
        for i in range(len(p), len(s)):
            # 添加新字符
            window_count[ord(s[i]) - ord('a')] += 1
            # 移除旧字符
            window_count[ord(s[i - len(p)]) - ord('a')] -= 1
            
            # 检查是否匹配
            if p_count == window_count:
                result.append(i - len(p) + 1)
        
        return result

public class Solution {
    public IList<int> FindAnagrams(string s, string p) {
        var result = new List<int>();
        if (s.Length < p.Length) return result;
        
        int[] pCount = new int[26];
        int[] windowCount = new int[26];
        
        // 统计p中字符频次
        foreach (char c in p) {
            pCount[c - 'a']++;
        }
        
        // 初始化窗口
        for (int i = 0; i < p.Length; i++) {
            windowCount[s[i] - 'a']++;
        }
        
        // 检查初始窗口
        if (ArraysEqual(pCount, windowCount)) {
            result.Add(0);
        }
        
        // 滑动窗口
        for (int i = p.Length; i < s.Length; i++) {
            // 添加新字符
            windowCount[s[i] - 'a']++;
            // 移除旧字符
            windowCount[s[i - p.Length] - 'a']--;
            
            // 检查是否匹配
            if (ArraysEqual(pCount, windowCount)) {
                result.Add(i - p.Length + 1);
            }
        }
        
        return result;
    }
    
    private bool ArraysEqual(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.Length; i++) {
            if (arr1[i] != arr2[i]) return false;
        }
        return true;
    }
}

var findAnagrams = function(s, p) {
    if (s.length < p.length) return [];
    
    const result = [];
    const pCount = new Array(26).fill(0);
    const windowCount = new Array(26).fill(0);
    
    // 统计p中字符频次
    for (let c of p) {
        pCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    // 初始化窗口
    for (let i = 0; i < p.length; i++) {
        windowCount[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    // 检查初始窗口
    if (arraysEqual(pCount, windowCount)) {
        result.push(0);
    }
    
    // 滑动窗口
    for (let i = p.length; i < s.length; i++) {
        // 添加新字符
        windowCount[s[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
        // 移除旧字符
        windowCount[s[i - p.length].charCodeAt(0) - 'a'.charCodeAt(0)]--;
        
        // 检查是否匹配
        if (arraysEqual(pCount, windowCount)) {
            result.push(i - p.length + 1);
        }
    }
    
    return result;
};

function arraysEqual(arr1, arr2) {
    for (let i = 0; i < arr1.length; i++) {
        if (arr1[i] !== arr2[i]) return false;
    }
    return true;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
滑动窗口O(n)O(1)

其中 n 是字符串 s 的长度。空间复杂度为 O(1) 是因为只使用了固定大小的数组（26个字母）。

相关题目