LeetCode 438. 找到字符串中所有字母异位词（python）

题目链接

题目描述：

给定一个字符串 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” 的字母异位词。

解题思路：

分别用两个数组ss，pp表示s中与p长度相同的子串中各个字母的个数，以及p中各个字母的个数，用数组的索引表示字母（0表示a，以此类推）

设置两个指针分别表示子串的开头和末尾，对于s中的子串，动态的改变ss中各个字母的个数，如果ss与pp相等，说明是字母异位词，将子串的左指针添加到返回值中。

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ss,pp=[0]*26,[0]*26
        for i in p:
            pp[ord(i)-ord('a')]+=1
        for i in s[0:len(p)]:
            ss[ord(i)-ord('a')]+=1
        l,r=0,len(p)-1
        res=[]
        while r <len(s)-1:
            if ss==pp:#是字母异位词
                res.append(l)
            ss[ord(s[l])-ord('a')]-=1
            l+=1
            r+=1            
            ss[ord(s[r])-ord('a')]+=1
        if ss==pp:
            res.append(l)
        return res

评论区答案：

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        
        if len(p) > len(s):
            return []
        
        s_map, p_map = [0]*128, [0]*128
        for i in range(len(p)):
            s_map[ord(s[i])], p_map[ord(p[i])] = s_map[ord(s[i])]+1, p_map[ord(p[i])]+1
        
        res = []
        if s_map == p_map:
            res.append(0)
        
        for i in range(1, len(s)-len(p)+1):
            s_map[ord(s[i+len(p)-1])] += 1
            s_map[ord(s[i-1])] -= 1
            if s_map == p_map:
                res.append(i)
        
        return res