当前位置：首页 > article >正文

【力扣100】8.找到字符串中所有字母异位词

article 2024/9/22 7:26:22

添加链接描述

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        sildingstr=''
        result=[]
        p=''.join(sorted(p))
        for i in range(len(s)):
            if len(sildingstr)<len(p):
                sildingstr=sildingstr+s[i]
                # print(sildingstr)
            if len(sildingstr)==len(p):
                sort_sildingstr=''.join(sorted(sildingstr))
                if sort_sildingstr==p:
                    result.append(i-len(p)+1)
                    sildingstr=sildingstr[1:]
                else:
                    sildingstr=sildingstr[1:]
        return result

思路：

纯正的滑动窗口
笑死我了，差点超时，怎么可以这么慢！！！

优化：

使用哈希表作为判断工具，这样就可以不对字符串进行排序

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n, m, res = len(s), len(p), []
        if n < m: return res
        p_cnt = [0] * 26
        s_cnt = [0] * 26
        for i in range(m):
            p_cnt[ord(p[i]) - ord('a')] += 1
            s_cnt[ord(s[i]) - ord('a')] += 1
        if s_cnt == p_cnt:
            res.append(0)
        
        for i in range(m, n):
            s_cnt[ord(s[i - m]) - ord('a')] -= 1
            s_cnt[ord(s[i]) - ord('a')] += 1
            if s_cnt == p_cnt:
                res.append(i - m + 1)
        return res