# Leetcode 438. Find All Anagrams in a String

## 題解

### 哈希表比對

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len = len(s)
        p_len = len(p)
        s_count = {}
        p_count = {}
        output = []

        if p_len > s_len:
            return output
        
        for i in range(ord('a'),ord('z') + 1):
            s_count[chr(i)] = 0
            p_count[chr(i)] = 0
        
        for i in range(0, p_len):
            s_count[s[i]] += 1
            p_count[p[i]] += 1
        
        if s_count == p_count:
            output.append(0)
        
        left = 0
        right = p_len - 1
        while right < s_len - 1:
            s_count[s[left]] -= 1
            left += 1
            right += 1
            s_count[s[right]] += 1
            if s_count == p_count:
                output.append(left)
        return output

### Diff 比對 (leetcode 30 解題基礎)

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        sn = len(s)
        pn = len(p)
        output = []
        mem = [0] * 26
        diff = 0

        if sn < pn:
            return output

        for i in range(pn):
            si = ord(s[i]) - 97
            pi = ord(p[i]) - 97
            mem[si] += 1
            mem[pi] -= 1
        
        diff = 0

        for c in mem:
            if c != 0:
                diff += 1
        
        if diff == 0:
            output.append(0)
        
        for i in range(sn - pn):
            si = ord(s[i]) - 97
            pi = ord(s[i + pn]) - 97
            if mem[si] == 1:
                diff -= 1
            elif mem[si] == 0:
                diff += 1
            mem[si] -= 1

            if mem[pi] == -1:
                diff -= 1
            elif mem[pi] == 0:
                diff += 1
            mem[pi] += 1

            if diff == 0:
                output.append(i+1)
        
        return output