E-438. Find All Anagrams in a String

Loading...LeetCode

这是个滑动窗口的问题:

Window Sliding Technique - GeeksforGeeksGeeksforGeeks

Loading...LeetCode

滑动窗口题模板↑

一种方法的视频讲解:

#0 暴力, TLE, 略

# 2 Sliding window method 1
'''
    这个方法就是视频里的方法, 我觉得是这题最好的解法
    https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/92059/O(n)-Sliding-Window-JAVA-Solution-Extremely-Detailed-Explanation
'''
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        dict_s = dict(zip(range(0, 26), [0]*26))
        dict_p = dict(zip(range(0, 26), [0]*26))
        for char in p:
            dict_p[ord(char)-ord('a')] += 1
        
        res = []
        step = len(p)
        
        for i in range(0, len(s)):
            if i >= step:
                dict_s[ord(s[i-step])-ord('a')] -= 1
            
            dict_s[ord(s[i])-ord('a')] += 1
            
            if dict_s == dict_p:
                res.append(i + 1 - step)
        
        return res
                    
# 2 自己写的:
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        dict_s = dict(zip(range(0,26),[0]*26))
        dict_p = dict(zip(range(0,26),[0]*26))
        
        step = len(p)
        res = []
        
        for char in p:
            dict_p[ord(char)-ord('a')] += 1
        
        for char in s[0:step]:
            dict_s[ord(char)-ord('a')] += 1
            
        if dict_s == dict_p:
            res.append(0)
            
        for i in range(step, len(s)):
            dict_s[ord(s[i])-ord('a')] += 1
            dict_s[ord(s[i-step])-ord('a')] -= 1
            if dict_s == dict_p:
                res.append(i + 1 - step)
                
        return res
        
# 3 Sliding window method 2
'''
我的解释:
    begin是窗口左边界, end是窗口右边界, counter是map里value非0的item的数量(此题counter最多是
    26个(即26个字母作为key, 最多有26个item)), map代表此时缺少的字符以及相应的数量
    (如果是负数, 就是当前多余的字符)
    
    思路就是end不断右移, 消耗map里的字符(遇到end上的字符, 就从map中减1), 直到map里的
    字符value都小于等于0; 再把begin右移, 补充map里的字符(遇到begin上的字符, 就从map
    中加1), 直到map里有一个字符的 value = 1 (下面写的是>0, 但是和=1等价, 因为counter等于0时
    才循环)时, 此时, 我们可以知道, 在s中, begin和end中间的部分(即,s[begin:end], 左闭右开)
    消耗了p所有的char, 至于是否恰好消耗, 我们用end-begin == len(p)进行判断=>如果相等, 则说明
    s[begin:end]恰好消耗了p, which means s[begin:end]和p互为Anagram.
      
    例子:
    s = a a c c a e a b c b a a
    p = a b a c
    map = {a:2, b:1 c:1}, 
    begin, end = 0
'''
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = []
        if len(p) > len(s):
            return res
        map = {}
        
        for char in p:
            map[char] = map.get(char, 0) + 1
        
        counter = len(map)
        
        begin, end = 0, 0
        head = 0
        
        while end < len(s):
            c = s[end]
            if c in map:
                map[c] -= 1
                if map[c] == 0:
                    counter -= 1
            end += 1
            
            while counter == 0:
                tempc = s[begin]
                if tempc in map:
                    map[tempc] += 1
                    if map[tempc] > 0:
                        counter += 1
                    
                if end-begin == len(p):
                    res.append(begin)
                    
                begin += 1
        
        return res

# 3 另一个方法
'''
    https://www.programiz.com/python-programming/methods/built-in/hash
    hash函数返回唯一hash value, 所以如果是anagram, 那么两个string中每一个char的hash
    值应该相等, 所以这也是一种滑动窗口的方法, 而且更快. 但是可能存在隐患就是, 如果把里面的
    hash替换成ord, 就能知道, 可能会存在ord值恰好相等的情况, 比如test case为"af"和"be"
    的时候, 那么hash值会不会也出现这种情况呢? 虽然大概率不会, 但是不是百分之百.
'''
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        res = []
        if len(p) >len(s):
            return res

        hash_p =hash_s = 0
        for i in range(len(p)):
            hash_p += hash(p[i])
            hash_s += hash(s[i])

        if hash_p==hash_s:
            res.append(0)

        for i in range(len(p), len(s)):
            hash_s += hash(s[i]) - hash(s[i-len(p)])
            if hash_p == hash_s:
                res.append(i- len(p)+1)

        return res