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

题目链接:Hot100-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 仅包含小写字母

解题思路

题目可理解为，在字符串\(s\)中找到一个长度等于字符串\(p\)的子串，使得该子串中的字母和字符串\(p\)中的字母一致。这样题目就变成了定长滑动窗口。

定长滑动窗口的解题步骤分为以下三步：

• 构建：构建一个大小为要求长度的窗口
• 判断：判断该窗口是否符合题意
• 滑动：当前窗口判断完毕，滑动当前窗口的起始至下一个位置，完成新的一轮构建

重复上述步骤，直到字符串中所有窗口被判断完为止。

对于此题，要判断子串和字符串\(p\)中的字母是否一致，可以定义两个字典，分别记录字母个数，当两个字典相等时，就代表此时的子串符合题意，并把当前子串的开头索引加入答案列表中。

假设字符串\(p\)的大小为\(k\)，当前窗口的末尾位置为\(right\)，那么当前窗口的开头位置为: \[ left = right - k + 1 \] 想象一个大小为2的定长窗口即可理解该公式。

具体代码

class Solution:
     def findAnagrams(self, s: str, p: str) -> List[int]:
            #定义答案列表和子字符串长度
            ans,k = [],len(p)
            #定义两个字典
            dics = DefaultDict(int)
            dicp = DefaultDict(int)
            #先统计p中的字母
            for i in p:
                dicp[i] += 1
            #统计s中的字母
            for right,j in enumerate(s):
                dics[j] += 1
                #首先构建一个窗口
                if right < k - 1:
                    continue
                #窗口构建完毕，如果符合题意，将索引加入答案列表
                if dics == dicp:
                    ans.append(right - k + 1)
                #构建下一个窗口前先毁坏当前窗口
                dics[s[right - k + 1]] -= 1
                if dics[s[right - k + 1]] == 0:
                    del dics[s[right - k + 1]]
            return ans

复杂度分析

• 时间复杂度：假设\(s\)的长度为\(lens\)，\(p\)的长度为\(lenp\)。依题意,\(lens>lenp\)，算法的时间复杂度主要在遍历\(s\)，故时间复杂度为\(0（lens）\)。
• 空间复杂度：同上，空间复杂度主要在两个字典，故空间复杂度为\(O(lens)\)。