2023.02.05 Today's Challenge

fabichoi 2023. 2. 5. 23:45

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

Find All Anagrams in a String - LeetCode

Find All Anagrams in a String - Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase

leetcode.com

1. 해시맵 생성 : p는 key로, 빈도수는 values로
2. s에 대해 슬라이딩 윈도우 기법 적용

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        hm, res, pl, sl = defaultdict(int), [], len(p), len(s)
        if pl > sl:
            return []
        
        for ch in p:
            hm[ch] += 1
        
        for i in range(pl - 1):
            if s[i] in hm:
                hm[s[i]] -= 1
            
        for i in range(-1, sl-pl + 1):
            if i > -1 and s[i] in hm:
                hm[s[i]] += 1
            if i+pl < sl and s[i+pl] in hm:
                hm[s[i+pl]] -= 1
            
            if all(v == 0 for v in hm.values()):
                res.append(i+1)
        
        return res