[HashMap 문제] Leetcode 438. Find All Anagrams in a String

문제

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

상기 문제는 p 문자의 각 글자를 재배치하여 s 문자 내 모든 시작 위치를 반환하는 문제이다.

문제풀이

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        def isAnagram(cnt_s,cnt_p):
            for key,val in cnt_s.items():
                if key not in cnt_p:
                    return False
                else :
                    if val != cnt_p[key]:
                        return False
        cnt_p,len_p = Counter(p),len(p)
        cnt_s = Counter(s[0:len_p])
        ans=[]
        j=len_p-1
        for i in range(len(s)-len_p+1):
            if cnt_s==cnt_p:
                ans.append(i)         
            j+=1
            if j>=len(s):
                break
            cnt_s[s[j]]+=1       
            cnt_s[s[i]] -=1
            if cnt_s[s[i]]<=0:
                cnt_s.pop(s[i])
           
        
        return ans              

핵심 코드 설명

주어진 두 문자가 Anagram인지 판단하기 위해서는 각 문자별 갯수가 동일하면 위치만 변경하면 되기 떄문에 Anangram으로 판단할 수 있다.
따라서 핵심은 문자별 갯수를 Dictionary로 관리하는 방안이며 이를 위해 소스상 탐색을 진행하면서 새로 들어오는 문자에 대해서는 갯수를 +1해주고 나가는 문자에 대해서는 갯수를 -1 감소시켜가면 Anagram인지 판단한다.

Lookback

1. Hashmap, 즉 Dictionary로 처리시 어렵지 않게 해결 할 수 있었다.