[2025-09-24] Leetcode 438. 找到字符串中所有字母异位词

题目

438. 找到字符串中所有字母异位词
给定两个字符串 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 * 104
• s 和 p 仅包含小写字母

我的代码（Python）

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        result = []
        n = len(p)
        currMap = {}
        for c in p:
            if c in currMap:
                currMap[c] += 1
            else:
                currMap[c] = 1
        tarMap = {}
        startIdx = -1
        for i in range(len(s)):
            if startIdx == -1:
                startIdx = i
            if s[i] not in currMap:
                startIdx = -1
                tarMap = {}
            else:
                if s[i] in tarMap:
                    tarMap[s[i]] += 1
                    if tarMap[s[i]] > currMap[s[i]]:
                        while True:
                            currHead = s[startIdx]
                            tarMap[currHead] -= 1
                            startIdx +=1
                            if currHead == s[i]:
                                break
                else:
                    tarMap[s[i]] = 1
                if i - startIdx + 1 == n:
                    result.append(startIdx)

        return result

点评

官方的两种解法看起来都很绕。不过思路是一样的。
官方有一个巧妙的地方，就是用一个长度26的数组表示各个字母的数量；不过相对这也限制了算法的使用场景。