寻找字符串中所有变位词

题目描述：
给定一个字符串s和一个非空字符串p，找出s中所有是p的变位词的子串的起始索引。变位词指字母相同，但排列不同的字符串。

解题步骤：

1. 问题分析：

• 我们需要在字符串s中找出所有子串，这些子串是p的变位词
• 变位词意味着两个字符串包含的字符及其出现次数完全相同
• 输出结果是这些子串在s中的起始索引

2. 关键思路：

• 使用滑动窗口+双哈希表的方法
• 一个哈希表记录p中每个字符的出现次数
• 另一个哈希表记录当前窗口中每个字符的出现次数
• 通过比较两个哈希表来判断当前窗口是否是p的变位词

4. 详细步骤：

步骤1：初始化哈希表

from collections import defaultdict

def findAnagrams(s, p):
    if len(s) < len(p):
        return []
    
    # 记录p中字符频率
    p_count = defaultdict(int)
    # 记录当前窗口字符频率  
    window_count = defaultdict(int)
    
    # 初始化p的哈希表
    for char in p:
        p_count[char] += 1

步骤2：设置滑动窗口

    result = []
    left = 0
    # 窗口长度固定为p的长度
    window_size = len(p)
    
    # 初始化窗口
    for right in range(len(s)):
        # 添加右边界字符
        window_count[s[right]] += 1
        
        # 当窗口大小达到p的长度时，开始判断
        if right - left + 1 == window_size:
            # 比较两个哈希表
            if window_count == p_count:
                result.append(left)
            
            # 移动左边界，移除左边字符
            window_count[s[left]] -= 1
            if window_count[s[left]] == 0:
                del window_count[s[left]]
            left += 1

步骤3：优化比较效率
上面的比较window_count == p_count在Python中时间复杂度较高，我们可以使用计数变量来优化：

def findAnagrams_optimized(s, p):
    if len(s) < len(p):
        return []
    
    p_count = [0] * 26
    window_count = [0] * 26
    result = []
    
    # 记录p的字符频率
    for char in p:
        p_count[ord(char) - ord('a')] += 1
    
    left = 0
    match_count = 0  # 记录匹配的字符数量
    
    for right in range(len(s)):
        # 右边界字符
        right_char = s[right]
        right_index = ord(right_char) - ord('a')
        
        # 如果这个字符在p中存在
        if p_count[right_index] > 0:
            window_count[right_index] += 1
            if window_count[right_index] <= p_count[right_index]:
                match_count += 1
        
        # 当窗口大小等于p的长度时
        if right - left + 1 == len(p):
            # 如果所有字符都匹配
            if match_count == len(p):
                result.append(left)
            
            # 移动左边界
            left_char = s[left]
            left_index = ord(left_char) - ord('a')
            
            if p_count[left_index] > 0:
                window_count[left_index] -= 1
                if window_count[left_index] < p_count[left_index]:
                    match_count -= 1
            
            left += 1
    
    return result

5. 算法复杂度：

• 时间复杂度：O(n)，其中n是字符串s的长度
• 空间复杂度：O(1)，因为哈希表大小固定为26（小写字母）

6. 示例验证：

输入: s = "cbaebabacd", p = "abc"
输出: [0, 6]
解释:
起始索引 0: "cba" 是 "abc" 的变位词
起始索引 6: "bac" 是 "abc" 的变位词

这种方法通过滑动窗口和哈希表，高效地找到了所有的变位词子串，避免了暴力解法的重复计算。