438. Find All Anagrams In A String

438. Find All Anagrams In A String (Medium) 找到字符串中所有字母的异位词

题干

Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

• 1 <= s.length, p.length <= 3 * 104
• s and p consist of lowercase English letters.

解法

朴素解法

• 循环字符串，以p的长度为准，找到所有子字符串。
• 对这个子字符串和p分别排序，然后比较。若相等则记录当前循环下标

这个解法算是暴力解法了

• 时间复杂度：外部循环是O(n-m+1)，内部排序是O(mlogm)，两者相乘，综合O(nmlogm)
• 空间复杂度：O(m)

划动窗口解法

• 创建两个窗口数据结构（字母为key，次数为value），一个代表p，一个代表s中的len(p)长度的窗口。
• 对比这两个窗口值，若一致，记录下标；
• 移动窗口：s窗口最左边的字符舍弃（对应次数减一），然后增加新进元素次数

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans: List[int] = []
        n: int = len(s)
        m: int = len(p)
        if n < m:
            return ans
        
        sw_s: Dict[str, int] = defaultdict(int)
        sw_p: Dict[str, int] = defaultdict(int)
        for i in range(m):
            sw_p[p[i]] += 1
            sw_s[s[i]] += 1
        # 校验第一个窗口
        if sw_s == sw_p:
            ans.append(0)
        
        for j in range(m,n):
            # 先划动，再记录，保证记录所有可能
            sw_s[s[j-m]] -= 1
            sw_s[s[j]] += 1
            if sw_s[s[j-m]] == 0:
                sw_s.pop(s[j-m])
            if sw_s == sw_p:
                ans.append(j-m+1)
        return ans

无dict写法：因为都是小写字母，本身就是有顺序的，所以可以使用list代替dict（算法无改变，只是数据结构变了）

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans: List[int] = []
        n: int = len(s)
        m: int = len(p)
        if n < m:
            return ans
        
        # 26个英文字母，26个slot，下标就代表字母顺序
        sw_s: List[int] = [ 0 for x in range(26) ]
        sw_p: List[int] = [ 0 for x in range(26) ]

        # 构建窗口，逐个元素求和字符a的ascii码差值（正好等于上面数据结构下标）
        for i in range(m):
            sw_p[ord(p[i])-ord("a")] += 1
            sw_s[ord(s[i])-ord("a")] += 1
        # 校验第一个窗口
        if sw_s == sw_p:
            ans.append(0)
        
        for j in range(m,n):
            # 先划动，再记录，保证记录所有可能
            sw_s[ord(s[j-m])-ord("a")] -= 1
            sw_s[ord(s[j])-ord("a")] += 1
            if sw_s == sw_p:
                ans.append(j-m+1)
        return ans

• time cost: O(n)
• space cost: O(m)