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

难度: 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⁴
s 和 p 仅包含小写字母

注意：本题与主站 438 题相同： https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

Submission

运行时间: 47 ms

内存: 16.6 MB

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:  
        m, n = len(s), len(p)
        if n > m:
            return []

        ans = []
        cnt_s, cnt_p = [0] * 26, [0] * 26

        for i in range(n):
            cnt_s[ord(s[i]) - ord('a')] += 1
            cnt_p[ord(p[i]) - ord('a')] += 1
        
        if cnt_s == cnt_p:
            ans.append(0)

        for i in range(n, m):
            cnt_s[ord(s[i]) - ord('a')] += 1
            cnt_s[ord(s[i - n]) - ord('a')] -= 1

            if cnt_s == cnt_p:
                ans.append(i - n + 1)
        return ans

Explain

此题解采用滑动窗口和字符频率计数的方法来找出所有的字母异位词的起始索引。首先，如果字符串p的长度大于s，则直接返回空列表，因为s中不可能有p的异位词。然后，使用两个大小为26的数组cnt_s和cnt_p来统计窗口内s的字符频率和字符串p的字符频率。初始窗口大小为p的长度，逐一比较两个计数数组，如果相等，则将当前窗口的起始索引加入结果列表。随后，窗口向右滑动，每次移动更新窗口内的字符频率，继续比较和记录结果。

时间复杂度: O(m)

空间复杂度: O(1)

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:  
        m, n = len(s), len(p)
        if n > m:
            return []

        ans = []
        cnt_s, cnt_p = [0] * 26, [0] * 26

        for i in range(n):  # 初始化计数数组
            cnt_s[ord(s[i]) - ord('a')] += 1
            cnt_p[ord(p[i]) - ord('a')] += 1
        
        if cnt_s == cnt_p:
            ans.append(0)  # 初始窗口就是一个解

        for i in range(n, m):  # 滑动窗口
            cnt_s[ord(s[i]) - ord('a')] += 1  # 新字符加入窗口
            cnt_s[ord(s[i - n]) - ord('a')] -= 1  # 窗口最左侧字符移出

            if cnt_s == cnt_p:
                ans.append(i - n + 1)  # 窗口滑动后再次检查
        return ans

Explore

在这种场景下，由于只涉及小写英文字母（a到z），我们可以直接使用一个固定大小为26的数组来映射每个字母的频率，其中数组的索引（0到25）直接对应字母'a'到'z'。使用数组的好处包括：1. 访问速度快，数组的访问时间复杂度为O(1)；2. 内存使用更高效，因为数组不需要额外的存储空间来维护键和结构本身；3. 实现简单，易于通过简单的算术运算（ord(char) - ord('a')）计算索引。而使用哈希表虽然灵活且可以应对更广泛的字符类型，但在这个特定问题中，它带来的额外内存和可能的较慢访问速度并不是必须的。

滑动窗口算法通过每次只更新进入和离开窗口的字符来减少不必要的计算。具体来说，在这个题解中，当窗口向右滑动时，只需要做两件事：增加新字符的频率计数，减少离开字符的频率计数。这种方法相比重新计算整个窗口的字符频率更高效，因为它避免了每次窗口移动时对所有字符进行全面重新计数的开销，大大减少了计算量。这使得时间复杂度降低，特别是在字符串s较长时，效率提升尤为明显。

现有的解决方案假设输入字符串仅包含小写英文字母，因此直接使用大小为26的数组来记录字符频率。如果输入字符串s包含非小写字母的字符，这种方法将不再适用。这是因为数组的索引计算（ord(char) - ord('a')）可能会得到负值或超出25的值，导致数组越界错误。在这种情况下，我们需要使用更通用的数据结构，例如哈希表，来适应所有可能的字符。哈希表能够动态地存储和查找任何字符的频率，不受字符种类的限制。