[LeetCode] 438. Find All Anagrams in a String

Sliding Window 알고리즘과 HashMap (파이썬에서는 dictionary로 구현) 자료구조에 대한 이해가 필요한 문제였습니다.

https://leetcode.com/problems/find-all-anagrams-in-a-string

문제 핵심

• 일반적인 반복문 또는 Two pointer 기법을 사용하면 time limit
• 따라서 계산 횟수를 최소화 하는 기법을 사용해야 함
• Two pointer 알고리즘과 비슷한 Sliding Window 알고리즘을 사용해야 한다
• 두 개의 해쉬맵을 만들어 계산을 간소화

---

솔루션

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        
        s_length, p_length = len(s), len(p)
        answer = []

        if s_length < p_length:
            return answer
        
        # create hashMap
        hashMap = {}
        for index, key in enumerate(p):
            if key not in hashMap:
                hashMap[key] = 1
            else:
                hashMap[key] += 1
        
        # create another hashmap which updated in every loop
        hashMap_tmp = {}
        for index in range(p_length):
            if s[index] not in hashMap_tmp:
                hashMap_tmp[s[index]] = 1
            else:
                hashMap_tmp[s[index]] += 1

        # loop and compare updated hashMap and orignal hashMap
        for s_index in range(0, s_length - p_length +1):
            # comapare two hashMap
            if hashMap == hashMap_tmp:
                answer.append(s_index)

            if s_index == s_length-p_length:
                break
            
            # update hashMap_tmp
            # delete first char from hashMap_tmp
            if s[s_index] in hashMap_tmp:
                if hashMap_tmp[s[s_index]] == 1:
                    del hashMap_tmp[s[s_index]]
                else:
                    hashMap_tmp[s[s_index]] -= 1
            else:
                hashMap_tmp[s[s_index]] = 1
            # add new char to hashMap_tmp
            if s[s_index + p_length] not in hashMap_tmp:
                hashMap_tmp[s[s_index + p_length]] = 1
            else:
                hashMap_tmp[s[s_index + p_length]] += 1
            
        return answer

---

참고

https://www.youtube.com/watch?v=G8xtZy0fDKg&t=417s 

문제를 이해하는 데 많은 도움이 되었습니다.