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

description

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

example

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

---

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Solution

Code

from collections import Counter

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        N, n = len(s), len(p)
        anagrams = dict(Counter(p))
        pointer = 0
        result = []
        
        while pointer < N :
            ch = s[pointer]
            if pointer >= n and s[pointer-n] in anagrams :
                anagrams[s[pointer-n]] += 1
            if ch in anagrams :
                anagrams[ch] -= 1
                if set(anagrams.values()) == {0} : result.append(pointer-n+1)
            pointer += 1
        
        return result

explaination

두 번의 시간초과 끝에 얻은 Aceept!

시간초과가 난 코드는 O(N^2)으로 substring을 잘라낸 후 substring을 순회하면서 string p와 동일한 문자들로 구성되어 있는지 체크했다. 시간초과가 났다. 🥲

개선한 최종코드는 위와 같다. 로직을 설명하자면, 각 문자의 개수만큼 가지는 anagrams의 value를 조절하면서 모든 value가 0일 때를 찾는 로직이다. 일단 포인터는 0부터 증가하는데 포인터 인덱스를 가지는 문자를 ch라 한다. 만약 포인터가 p의 길이보다 크거나 같은 경우에는 빠지는 문자가 생긴다. 포인터에서 n을 뺀 인덱스의 문자가 존재한다면 다시 +1을 해주어야 한다. ch가 anagrams에 존재하면 ch를 키로 가지는 value를 -1해준다. 그리고 집합 자료형을 이용해서 {0}일 때는 모두가 0인 것이므로 결과값에 더해준다!

딕셔너리와 집합 자료형을 이용하여 시간복잡도를 줄인 케이스 😎