[LeetCode] 438. Find All Anagrams in a String

- Problem

438. Find All Anagrams in a String

두 개의 문자열 s, p가 주어졌을 때, s에서 p의 anagram의 모든 시작 인덱스의 배열을 반환하는 문제다.

---

- 내 풀이 1 (Brute-Force)

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        M, N = len(s), len(p)
        cnt = Counter(p)
        return [i for i in range(M-N+1) if Counter(s[i:i+N]) == cnt]

- 결과

이게 되네?

주어진 문자열의 길이가 최대 3*10^4 이므로, 브루트포스 풀이 방식은 당연히 TLE가 날 줄 알았는데 이게 된다.

---

- 내 풀이 2 (hash)

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

        if M < N: 
            return []
        
        cnt = Counter(p) # O(N)

        for i in range(N): # O(N)
            if s[i] in cnt: 
                cnt[s[i]] -= 1

        for i in range(M-N+1): # O(M-N)
            if not any(cnt.values()): # O(26): alphabet => O(1)
                answer.append(i)

            if s[i] in cnt:
                cnt[s[i]] += 1

            if i+N < M and s[i+N] in cnt: 
                cnt[s[i+N]] -= 1
                
                
        return answer

- 결과

이 분의 코드를 참고했다. (베꼈다.)

이 문제의 시간 복잡도는 주어진 문자열 중 p의 길이에 영향을 받는다.
따라서, 시간 복잡도는 O(N)이다.

맞을까?

또한, if not any(cnt.values()): 줄에서 시간 복잡도가 O(N)이라고 생각할 수도 있으나, cnt의 길이는 최대 26(알파벳 개수)이므로, O(26) -> O(1) 상수 시간을 가진다.