LeetCode 热题100 438. 找到字符串中所有字母异位词

LeetCode 热题100 | 438. 找到字符串中所有字母异位词

大家好，今天我们来解决一道经典的算法题——找到字符串中所有字母异位词。这道题在 LeetCode 上被标记为中等难度，要求我们在字符串 s 中找到所有是 p 的异位词的子串，并返回这些子串的起始索引。下面我将详细讲解解题思路，并附上 Python 代码实现。

题目描述

给定两个字符串 s 和 p，找到 s 中所有是 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例：

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba"，它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac"，它是 "abc" 的异位词。

解题思路

这道题的核心是找到 s 中所有与 p 的字符组成相同的子串。我们可以使用 滑动窗口 和 哈希表 来解决这个问题。

核心思想

1. 滑动窗口：

   • 使用一个固定大小的窗口（大小为 p 的长度）在 s 上滑动。
   • 检查窗口内的字符是否与 p 的字符组成相同。

2. 哈希表：

   • 使用两个哈希表（或数组）分别记录 p 的字符频率和当前窗口的字符频率。
   • 如果两个哈希表相等，则当前窗口是 p 的异位词。

代码实现

from collections import defaultdict

def findAnagrams(s, p):
    """
    :type s: str
    :type p: str
    :rtype: List[int]
    """
    result = []  # 存储结果的起始索引
    len_s, len_p = len(s), len(p)
    
    # 如果 s 的长度小于 p 的长度，直接返回空列表
    if len_s < len_p:
        return result
    
    # 初始化 p 的字符频率哈希表
    p_count = defaultdict(int)
    for char in p:
        p_count[char] += 1
    
    # 初始化滑动窗口的字符频率哈希表
    window_count = defaultdict(int)
    for i in range(len_p):
        window_count[s[i]] += 1
    
    # 滑动窗口
    for i in range(len_s - len_p + 1):
        # 如果当前窗口的字符频率与 p 的字符频率相等，记录起始索引
        if window_count == p_count:
            result.append(i)
        
        # 移动窗口
        if i + len_p < len_s:  #如果 i + len_p >= len_s，说明窗口已经到达 s 的末尾，无法再向右移动。
            window_count[s[i]] -= 1
            if window_count[s[i]] == 0:
                del window_count[s[i]]
            window_count[s[i + len_p]] += 1
    
    return result

代码解析

1. 初始化：

   • 如果 s 的长度小于 p 的长度，直接返回空列表。
   • 使用 defaultdict 初始化 p 的字符频率哈希表 p_count。

2. 滑动窗口：

   • 初始化滑动窗口的字符频率哈希表 window_count，记录窗口内的字符频率。
   • 遍历 s，每次移动窗口时：
     • 如果 window_count 和 p_count 相等，则当前窗口是 p 的异位词，记录起始索引。
     • 移动窗口：移除左边界字符，加入右边界字符。

3. 返回结果：

   • 返回所有符合条件的起始索引。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。我们只需要遍历 s 一次。
• 空间复杂度：O(1)，因为字符集大小固定（小写字母，最多 26 个），哈希表的大小是常数。

示例运行

示例 1

# 输入: s = "cbaebabacd", p = "abc"
s = "cbaebabacd"
p = "abc"
print(findAnagrams(s, p))  # 输出: [0, 6]

解释：

• 起始索引等于 0 的子串是 "cba"，它是 "abc" 的异位词。
• 起始索引等于 6 的子串是 "bac"，它是 "abc" 的异位词。

示例 2

# 输入: s = "abab", p = "ab"
s = "abab"
p = "ab"
print(findAnagrams(s, p))  # 输出: [0, 1, 2]

解释：

• 起始索引等于 0 的子串是 "ab"，它是 "ab" 的异位词。
• 起始索引等于 1 的子串是 "ba"，它是 "ab" 的异位词。
• 起始索引等于 2 的子串是 "ab"，它是 "ab" 的异位词。

总结

通过滑动窗口和哈希表，我们可以高效地找到 s 中所有是 p 的异位词的子串。这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)，能够处理较大的输入规模。希望这篇题解对你有帮助！如果还有其他问题，欢迎继续提问！

关注我，获取更多算法题解和编程技巧！