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

<https://leetcode-cn.com/problems/find-all-anagrams-in-a-string>

## 题目描述

```
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 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" 的字母异位词。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```

## 思路

看完题目思路也很清晰了，就是用定宽的滑动窗口；而字母异位词，用大白话来说就是两个字符串包含的各种字母数量都相等。

接着第二个问题是，用什么方式来记录窗口中各个字母出现的次数？

哈希表是比较一个比较符合直觉的想法。

还有一种就是用数组。因为字符串中只包含小写字母，也就是只有 26 种字母，所以我们可以使用一个长度为 26 的数组来记录，数组下标表示字母，值则表示字母出现的次数。

## 复杂度

* 时间复杂度：$O(n)$，n 为字符串 s 的长度，使用滑动窗口只需要遍历一次 s，而比较窗口中字母数量和字符串 p 中字母数量的操作，虽然也用到了循环，但最多也就是 26 次，所以最终的时间复杂度还是 $O(n)$。
* 空间复杂度：$O(1)$，用到了两个长度为 26 的数组来记录字母出现次数以及若干个指针，但这些都与输入的字符串长度规模无关，是常数级别的空间，所以最终的空间复杂度还是 $O(1)$。

## 代码

Python Code

```python
class Solution(object):
    def isSame(self, a, b):
        for i in range(0, len(a)):
            if a[i] != b[i]: return False
        return True

    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        if not s or not p or len(s) < len(p): return []

        a = ord('a')
        # 计算字符串 p 中的字母数量
        countP = [0 for _ in range(26)]
        for c in p:
            countP[ord(c) - a] += 1

        # 在 s 中先滑出一个窗口，计算窗口中的字母数量
        countS = [0 for _ in range(26)]
        for k in range(0, len(p)):
            countS[ord(s[k]) - a] += 1

        ans = []
        # 比较窗口中的字母数量和字符串 p 中的字母数量
        if (self.isSame(countP, countS)):
            ans.append(0)

        # 继续向右滑动窗口，更新 -> 比较
        i, j = 0, len(p) - 1
        while j < len(s) - 1:
            countS[ord(s[i]) - a] -= 1
            i += 1
            j += 1
            countS[ord(s[j]) - a] += 1
            if (self.isSame(countP, countS)):
                ans.append(i)
        return ans
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://suki.gitbook.io/91-days-algorithm/topics/day-69.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.